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

Question

我正在尝试制作一个可以解决迷宫问题的应用程序，我正在尝试使用回溯技术实现它。

我开发了一个代码，适用于一些简单的场景，但至少在一个更复杂的场景中失败了。

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

关于代码

所以我有两种方法 initializeMaze1 和 initializedMaze2 只是加载一些预设场景（起点，一些墙和终点).

我对第一个没问题，但第二个就变了。

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

我也有净化的印刷方法

最后是迷宫法，也就是回溯代码。参数为：

生成的迷宫（就是我之前讲过的方法）
"player" 在迷宫行中的位置。
"player" 在迷宫列中的位置。
解决方案。这是另一个矩阵，它将给出玩家的路径，所以我将在其中标记移动，并且我将保留原始迷宫。

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

回溯代码

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

我有一个 isFactible 方法来分析运动并判断它是否正常（如果撞墙或超出限制）。

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

如果不符合事实并且我们完成循环，取消标记实际位置和 return 一个错误值（因此其他上下文将知道它）。

如果可行，我们将标记新位置，我们需要区分两种可能性：

我们要移动的位置是终点（目标或出口），所以我们成功了。
我们要移动的位置不是结束，所以我们再次递归调用我们已经移动的新位置。

下面说说我发现的问题

问题

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

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;
}

}

Answer 1

与您（想像您）解决真正的迷宫一样。

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

当您 return 到一个位置（应该允许重新访问）时，将已经尝试过的方向视为与墙相同的方式 - 即它是无效的。

当你没有更多有效方向时return你来的路。

所以与您的代码的唯一区别是记住每个位置的 'tried and failed' 方向。这应该足以防止递归。

Answer 2

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

Answer 3

正如 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 函数 returns 如果下一步的 solution 不等于 1.

，则为 false

希望对您有所帮助。

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

Problem about maze resolution with backtracking java

java

maze

backtracking