关于回溯java的迷宫解决问题

问题描述 投票：1回答：3

我正在尝试制作一个应该解决迷宫问题的应用程序，而我正试图通过回溯tecnique来实现它。

我已经开发了一个代码，并且适用于一些简单的场景但是失败了，至少是一个复杂的。

在我公开代码和具体问题之前，我想解释它是如何工作的。

关于代码

所以我有两个方法initializeMaze1和initializedMaze2，它只是加载一些预设场景（起点，一些墙和终点）。

我对第一个问题没有任何问题，但第二个问题发生了变化。

那些方法给我一个整数矩阵，它代表实体（墙，起点......）。

我还有一种用于净化的印刷方法。

最后是迷宫方法，它是回溯代码。参数是：

  1. 生成的迷宫（通过我之前谈到的方法完成）。
  2. 迷宫行中“玩家”的位置。
  3. 迷宫中“玩家”的位置。
  4. 解决方案。这是另一个矩阵，它将给出玩家的路径，所以我将在那里标记动作，并且我将使原始迷宫无法接近。

现在，我将更深入地讨论回溯代码。

回溯代码

所以这个方法是一个for循环尝试一些尝试（尝试可能是玩家的动作）所以我们尝试每个人，直到我们获得有效的运动或返回，因为没有可能的有效运动。

我有一个isFactible方法，它分析运动并说明它是否正常（如果与墙碰撞或超出限制）。

如果不可移动，则尝试其他移动（增加for循环的迭代变量）。

如果不可接受并且我们完成循环，则指出实际位置并返回假值（因此其他上下文将知道它）。

如果是可以接受的，我们将标记新的位置，我们需要区分两种可能性：

  • 我们将要移动的位置是结束（目标或退出），我们是否成功。
  • 我们要移动的位置不是结束，所以我们再次递归地调用我们已经移动的新位置。

现在我要谈谈我发现的问题。

问题

当我加载第二个迷宫时，我们有这样的场景：

S：开始吧。 E：空。 W：墙。 F：完成。

| S | E | W | W |

| E | E | E | E |这是问题所在

| E | E | W | W |

| W | E | E | F |

所以代码，尝试先向右移动，如果没有，则尝试向下，如果没有尝试，则尝试向下移动，如果没有，则尝试向上移动。我们有预设运动。

所以向右移动，好吧。然后试图再次向右移动，但是有一堵墙。所以说，好吧。然后，向右移动直到最后一列。试图向右移动，他不能因为走了出去。试图向下移动，他不能，有一堵墙。试图向左移动，他可以，所以移动到那里。我有这个无限循环。

我想到的第一件事就是，好吧，只需添加更多限制，并避免他可以移动到他已经去过的地方。

但我不认为这是一个很好的解决方案。

你知道怎么解决这个问题吗？也许，如果我在代码中犯了一些错误，或者我选择的解决问题的策略不好，我将非常感谢您的意见。

谢谢你。

代码

import java.util.List;
import java.util.ArrayList;

public class maze {

private static final int START = 1;
private static final int END = 2;
private static final int WALL = 3;
private static final int EMPTY = 0;
private static final int MOVE_RIGHT = 5;
private static final int MOVE_DOWN = 6;
private static final int MOVE_LEFT = 7;
private static final int MOVE_UP = 8;

public static void main(String[] args)
{
    int[][] solution = {{1,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
    showInitializationMessage();
    print(solution);
    if(maze(initializeMaze2(),0, 0, solution))
    {
        print(solution);
    }
    else
    {
        System.out.println("There is no solution");
    }
}

private static void showInitializationMessage()
{
    System.out.println("MAZE APPLICATION");
    System.out.println("_________________");
    System.out.println();
    System.out.println();
}

private static void print(int[][] solution)
{
    for(int i=0; i<solution.length;i++)
    {
        for(int j=0;j<solution.length;j++)
        {
            System.out.print(solution[i][j]);
        }
        System.out.println();
    }
    System.out.println();
    System.out.println("____________________");
    System.out.println();
}

private static int[][] initializeMaze1()
{
    //Create the structure
    int[][] maze = new int[4][4];

    //Setting column 0
    maze[0][0]=START;
    maze[1][0]=EMPTY;
    maze[2][0]=EMPTY;
    maze[3][0]=WALL;

    //Setting column 1
    maze[0][1]=EMPTY;
    maze[1][1]=WALL;
    maze[2][1]=EMPTY;
    maze[3][1]=WALL;

    //Setting column 2
    maze[0][2]=EMPTY;
    maze[1][2]=WALL;
    maze[2][2]=WALL;
    maze[3][2]=EMPTY;

    //Setting column 3
    maze[0][3]=EMPTY;
    maze[1][3]=EMPTY;
    maze[2][3]=EMPTY;
    maze[3][3]=END;

    return maze;


}

private static int[][] initializeMaze2()
{
    //Create the structure
    int[][] maze = new int[4][4];

    //Setting column 0
    maze[0][0]=START;
    maze[1][0]=EMPTY;
    maze[2][0]=EMPTY;
    maze[3][0]=WALL;

    //Setting column 1
    maze[0][1]=EMPTY;
    maze[1][1]=EMPTY;
    maze[2][1]=EMPTY;
    maze[3][1]=EMPTY;

    //Setting column 2
    maze[0][2]=WALL;
    maze[1][2]=EMPTY;
    maze[2][2]=WALL;
    maze[3][2]=EMPTY;

    //Setting column 3
    maze[0][3]=WALL;
    maze[1][3]=EMPTY;
    maze[2][3]=WALL;
    maze[3][3]=END;

    return maze;


}

private static boolean checkNotOutOfBounds(int[][] maze,int stepX, int stepY, int movement )
{
    if(movement==MOVE_RIGHT)
    {
        if(stepY+1>maze.length-1)
        {
            return false;
        }
    }
    else if(movement==MOVE_DOWN)
    {
        if(stepX+1>maze[0].length)
        {
            return false;
        }
    }
    else if(movement==MOVE_LEFT)
    {
        if(stepY-1<0)
        {
            return false;
        }
    }
    else if(movement==MOVE_UP)
    {
        if(stepX-1<0)
        {
            return false;
        }
    }
    return true;
}

private static boolean checkNotCollideWithObstacle(int[][] maze, int stepX, int stepY , int movement)
{
    if(movement==MOVE_RIGHT)
    {
        if(maze[stepX][stepY+1]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_DOWN)
    {
        if(maze[stepX+1][stepY]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_LEFT)
    {
        if(maze[stepX][stepY-1]==WALL)
        {
            return false;
        }
    }
    else if(movement==MOVE_UP)
    {
        if(maze[stepX-1][stepY]==WALL)
        {
            return false;
        }
    }
    return true;
}

private static boolean checkValidMovement(int[][] maze, int stepX, int stepY , int movement)
{
    if(checkNotOutOfBounds(maze, stepX, stepY, movement) && checkNotCollideWithObstacle(maze, stepX, stepY, movement))
    {
        return true;
    }
    return false;
}

private static boolean isFactible(int[][] maze,int stepX, int stepY, int[][] solution, int attemp)
{
    if(attemp==0)
    {
        //MOVE RIGHT
        return checkValidMovement(maze, stepX, stepY, MOVE_RIGHT);
    }
    else if(attemp==1)
    {
        //MOVE DOWN
        return checkValidMovement(maze, stepX, stepY, MOVE_DOWN);
    }
    else if(attemp==2)
    {
        //MOVE LEFT
        return checkValidMovement(maze, stepX, stepY, MOVE_LEFT);
    }
    else if(attemp==3)
    {
        //MOVE UP
        return checkValidMovement(maze, stepX, stepY, MOVE_UP);
    }
    return false;
}

private static boolean maze(int[][] maze,int stepX, int stepY, int[][] solution)
{

    boolean success =false;
    for(int attempt=0; attempt<4 && !success; attempt++)
    {
        //solution[stepX][stepY]=attempt???
        if(isFactible(maze,stepX, stepY, solution,attempt))
        {
            mark(solution,stepX, stepY,attempt);
            print(solution);
            int updatedStepX = updateStepX(stepX, stepY, maze, attempt);
            int updatedStepY = updateStepY(stepX, stepY, maze, attempt);

            if(maze[updatedStepX][updatedStepY]==END)
            {
                success=true;
            }
            else
            {
                success = maze(maze, updatedStepX, updatedStepY, solution);
            }
        }

    }
    if(!success)
    {
        solution[stepX][stepY]=0;
        print(solution);



    }
    return success;
}

private static void mark(int[][] solution, int stepX, int stepY, int attempt)
{
    if(attempt==0)
    {
        solution[stepX][stepY+1]=1;
    }
    else if(attempt==1)
    {
        solution[stepX+1][stepY]=1;
    }
    else if(attempt==2)
    {
        solution[stepX][stepY-1]=1;
    }
    else if(attempt==3)
    {
        solution[stepX-1][stepY]=1;
    }
}

private static int updateStepX(int oldStepX, int oldStepY, int[][] maze, int attemp)
{
    int updatedStepX=0;
    if(attemp==1)
    {
        updatedStepX=oldStepX+1;
    }
    else if(attemp==3)
    {
        updatedStepX=oldStepX-1;
    }
    else
    {
        updatedStepX=oldStepX;
    }

    return updatedStepX;
}

private static int updateStepY(int oldStepX, int oldStepY, int[][] maze, int attempt)
{
    int updatedStepY=0;

    if(attempt==0)
    {
        updatedStepY=oldStepY+1;
    }
    else if(attempt==2)
    {
        updatedStepY=oldStepY-1;
    }
    else
    {
        updatedStepY=oldStepY;
    }

    return updatedStepY;
}

}

java backtracking maze
3个回答
2
投票

和你想的一样（想你）解决一个真正的迷宫。

对于每个位置，记录您从哪个方向到达以及您留下的（有效）方向（我想你离开之前）。

当您返回某个位置时（应该允许重新访问）以与墙相同的方式处理已经尝试过的方向 - 即它是无效的。

如果您没有更多有效的指示，请按照您的方式返回。

因此，与代码的唯一区别在于记住每个位置的“尝试失败”方向。这应该足以防止递归。

1
投票

我认为最简单的方法就是记住你最后一次出现的坐标。如果除了返回之外没有有效的移动，请返回并将您所在的位置标记为墙。最后你会到[F]。

1
投票

正如DrPhill所说，你必须跟踪你去过的地方。你已经在函数mark中这样做，但你没有在checkValidMovement函数中使用该信息。

您应该将该功能更改为如下所示：

private static boolean checkValidMovement(int[][] maze, int stepX, int stepY , int movement, int[][] solution)
  {
    if(checkNotOutOfBounds(maze, stepX, stepY, movement) 
        && checkNotCollideWithObstacle(maze, stepX, stepY, movement)
        && isNotYetVisited(maze, stepX, stepY, movement, solution))
    {
      return true;
    }
    return false;
  }

如果下一步的isNotYetVisited不等于solution，那么1函数返回false。

希望这可以帮助。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.