递归迷宫求解器不起作用

我已经查看了每个有这个问题的帖子，每个指南，每个算法，但我仍然找不到问题的答案。奇怪的是，它不会引起任何错误，但对于每个迷宫，它都说它是无法解决的，并将开始标记为死胡同。

我盯着我的代码几个小时，我无法弄清楚我做错了什么！我的代码：

(其他不重要的类 - MazeSymbol = 带有符号名称及其字符串的枚举，位置 = 行/列类，坐标 = 包含 MazeSymbol 和位置的类((

迷宫.java：

private Coordinate[][] map;
private Position start;
private Position goal;
private ArrayList<Coordinate> solutionPath;
boolean solveable;
public Maze(Coordinate[][] map, Position start, Position goal){
    this.start=start;
    this.map=map;
    this.goal=goal;
    this.solutionPath=new ArrayList<>();
    this.solveable = solveMaze(Coordinate.fromMaze(start, this)); //fromMaze takes a position and finds it's symbol.
}
public boolean isSolveable(){
    return solveable;
}
private boolean solveMaze(Coordinate c){
    System.out.println("Solving - "+c.getPosition().row+","+c.getPosition().column);
     if(!c.getPosition().isOnMaze(this)){//Checks if it is between the bounds of the maze (larger than 0 and smaller than length both for X and Y)
         System.out.println(c.getPosition().row+","+c.getPosition().column+"Isnt on maze! ");
         return false;
     }
     if(c.getPosition().equals(goal)){
         System.out.println(c.getPosition().row+","+c.getPosition().column+"Is goal!");
         return true;
     }
     if(!c.getSymbol().equals(MazeSymbol.OPEN)){//If it isnt an open path - walked/dead end/wall
         System.out.println(+c.getPosition().row+","+c.getPosition().column+" isn't open!(it's "+c.getSymbol()+")");
         return false;
     }
     map[c.getPosition().getRow()][c.getPosition().getColumn()] = new Coordinate(c.getPosition(), MazeSymbol.PATH);//Replace the open path sign with a walked path sign
     solutionPath.add(c);//Add the coordinate to the solution path
     if(solveMaze(c.setPosition(c.getPosition().positionAbove())))return true;//row-1                  
     if(solveMaze(c.setPosition(c.getPosition().positionLeft())))return true;//column+1
     if(solveMaze(c.setPosition(c.getPosition().positionBelow())))return true;//row+1
     if(solveMaze(c.setPosition(c.getPosition().positionRight())))return true;//column-1
     map[c.getPosition().getRow()][c.getPosition().getColumn()] = c.setSymbol(MazeSymbol.DEAD_END);//If none was the path, mark it as a dead end
     return false;
    }

请帮忙！当我插入这个极其简单的迷宫时：

{"O"，"W"，"W"}，

{"O"，"O"，"W"}，

{"W"，"O"，"O"}

它说它是无法解决的，输出：

新世界

哎呀

追求

提前感谢！

编辑：更改了此行

map[c.getPosition().getRow()][c.getPosition().getColumn()] = new Coordinate(c.getPosition(), MazeSymbol.PATH);

现在它根本不起作用，它只是在 2 行中给出一个 StackOverflowError

然后一遍又一遍地在第 3 行中给出：

System.out.println("Solving - "+c.getPosition().row+","+c.getPosition().column);
if(solveMaze(c.setPosition(c.getPosition().positionAbove())))return true;
if(solveMaze(c.setPosition(c.getPosition().positionRight())))return true;

我在这里猜测，因为您没有给我们确切的Coordinate代码，但是假设所有set操作实际上都设置了Coordinate实例中的信息，问题是您更改了此行中c的符号：

 map[c.getPosition().getRow()][c.getPosition().getColumn()] = c.setSymbol(MazeSymbol.PATH);//Replace the open path sign with a walked path sign

现在，您的c被标记为PATH而不是OPEN。然后进行递归调用。假设它到达了下面的方向，这是它应该看到它打开的地方。您设置了 c 的位置，但其值仍PATH 。然后，在递归步骤中，它到达

 if(!c.getSymbol().equals(MazeSymbol.OPEN)){//If it isnt an open path - walked/dead end/wall
     System.out.println(+c.getPosition().row+","+c.getPosition().column+" isn't open!(it's "+c.getSymbol()+")");
     return false;
 }

当然，价值并不OPEN.因此，该位置以及原始位置周围的所有其他位置都失败了。

您需要从新位置的实际地图更新c的值，但您不会这样做。

编辑

我看过你的问题编辑。您所做的确实阻止了程序陷入死胡同，但它实际上并没有解决问题。你看，现在发生的事情是你更新了地图中的位置，但是当你调用递归版本时，坐标会保留OPEN的值(或任何开始时的值(。

递归步骤中会发生什么？让我们忽略地图内没有的方向。它到了

 if(!c.getSymbol().equals(MazeSymbol.OPEN)){//If it isnt an open path - walked/dead end/wall
     System.out.println(+c.getPosition().row+","+c.getPosition().column+" isn't open!(it's "+c.getSymbol()+")");
     return false;
 }

但无论地图中该坐标处的实际内容如何，c的值仍然是OPEN。所以它不会进入这个if块。它认为它处于未平仓状态。所以它愉快地一次又一次地进入递归步骤。它会转到上面的位置，不管地图上说它是P，都会相信它处于打开的位置，然后再次递归，回到下面的位置，依此类推。

正如我上面已经说过的，你要做的是从地图的新位置更新 c 的值。基本上，您永远不会从地图上阅读。从不检查地图中的任何位置是墙、路径还是打开的位置。您只查看c，并且c不会从地图更新，因此它不会为您提供所需的信息。

我建议solveMaze应该采取位置而不是坐标，迷宫可以简单地是MazeSymbol[][]。

事实上，我根本看不到 Coordinate 类的用途 - 它似乎只是通过存储 MazeSymbol 的另一个实例来增加混乱，该实例可能与全局地图不同。我认为这是@RealSkeptic强调的问题，建议：

从地图的新位置更新 C 的值

我只是更进一步，根本不打扰坐标类。

这里的关键概念是，当您递归为尝试时，您将更新全局状态(迷宫图和解决方案路径(;当您递归于该尝试时，您将撤消这些更改。

然后 solveMaze 的递归部分变为：

private boolean solveMaze(Position p){
    if(!p.isOnMaze(this)) {
        return false;
    }
    if(p.equals(goal)) {
        return true;
    }
    if(!map[p.getRow()][p.getColumn()].equals(MazeSymbol.OPEN)) {   // See NOTE 1
        return false;
    }
    map[p.getRow()][p.getColumn()] = MazeSymbol.PATH;
    solutionPath.add(p);
    if(solveMaze(p.positionAbove())) return true;   // See NOTE 2
    if(solveMaze(p.positionLeft()))  return true;
    if(solveMaze(p.positionBelow())) return true;
    if(solveMaze(p.positionRight())) return true;
    solutionPath.remove(solutionPath.size() - 1);    // See NOTE 3
    map[p.getRow()][p.getColumn()] = MazeSymbol.DEAD_END;
    return false;
}

注 1：这将检查实际迷宫中的符号，而不是跨堆栈传递的临时坐标中的符号。

注2：我假设位置上方/左侧...方法都返回一个新的位置实例，并且不修改传递的实例;他们可能会这样做，但如果没有代码，我无法确定。

注 3：您需要从解决方案路径中删除无效尝试。

免责声明：没有编译/运行任何内容，只是在这里输入，所以可能包含错别字等。

呵

相关内容

最新更新

热门标签：