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

Question

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

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

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

关于代码

所以我有两种方法initializeMaze1 和initializedMaze2，它们只是加载一些预设场景(起点、一些墙和终点)。

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

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

我还有一个净化的打印方法。

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

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|

---

因此，代码首先尝试向右移动，如果不是，则尝试向下移动，如果不是，则尝试向左移动，如果不是，则尝试向上移动。我们有预设 Action 。

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

我首先想到的是，好吧，只是增加更多的限制，避免他可以移动他已经去过的地方。

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

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

谢谢你。

代码

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

就像您(自认为)解决真正的迷宫一样。

对于每个位置，记录您从哪个方向到达以及您离开哪个(有效)方向(我认为在您离开之前)。

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

当您没有更多有效方向时，请原路返回。

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