用递归算法在迷宫中寻找最短路径
我做了一个小的递归算法,以找到迷宫的解决方案,格式如下
###S###
##___##
##_#_##
#__#_##
#E___##
其中,“#”表示墙,“#”表示开放空间(可自由移动)。”S'表示开始位置,E'表示结束位置
我的算法运行得很好,但我想知道如何修改它以获得最短路径
/**
* findPath()
*
* @param location - Point to search
* @return true when maze solution is found, false otherwise
*/
private boolean findPath(Point location) {
// We have reached the end point, and solved the maze
if (location.equals(maze.getEndCoords())) {
System.out.println("Found path length: " + pathLength);
maze.setMazeArray(mazeArray);
return true;
}
ArrayList<Point> possibleMoves = new ArrayList<Point>();
// Move Right
possibleMoves.add(new Point(location.x + 1, location.y));
// Down Move
possibleMoves.add(new Point(location.x, location.y - 1));
// Move Left
possibleMoves.add(new Point(location.x - 1, location.y));
// Move Up
possibleMoves.add(new Point(location.x, location.y + 1));
for (Point potentialMove : possibleMoves) {
if (spaceIsFree(potentialMove)) {
// Move to the free space
mazeArray[potentialMove.x][potentialMove.y] = currentPathChar;
// Increment path characters as alphabet
if (currentPathChar == 'z')
currentPathChar = 'a';
else
currentPathChar++;
// Increment path length
pathLength++;
// Find the next path to traverse
if (findPath(potentialMove)) {
return true;
}
// Backtrack, this route doesn't lead to the end
mazeArray[potentialMove.x][potentialMove.y] = Maze.SPACE_CHAR;
if (currentPathChar == 'a')
currentPathChar = 'z';
else
currentPathChar--;
// Decrease path length
pathLength--;
}
}
// Previous space needs to make another move
// We will also return false if the maze cannot be solved.
return false;
}
在第一个街区中,我找到了路径并将其打断。还设置了写有路径的char[][]数组,该数组随后作为结果打印出来
它工作得很好,但我想知道什么是修改它的最佳方式,使它在找到第一条成功路径后不会崩溃,而是继续运行,直到找到可能的最短路径
我尝试过这样做,修改findPath()方法并添加一个shortestPath和hasFoundPath变量。第一个表示到目前为止找到的最短路径的长度,hasFoundPath变量表示是否找到任何路径
// We have reached the end point, and solved the maze
if (location.equals(maze.getEndCoords())) {
System.out.println("Found path length: " + pathLength);
// Is this path shorter than the previous?
if (hasFoundPath && pathLength < shortestPathLength) {
maze.setMazeArray(mazeArray);
shortestPathLength = pathLength;
} else if (!hasFoundPath) {
hasFoundPath = true;
maze.setMazeArray(mazeArray);
shortestPathLength = pathLength;
}
//return true;
}
但我还没能让它将Mazarray设置为它可能找到的任何最短路径的正确值
任何指导都将不胜感激:)谢谢
spaceIsFree()方法只需确保上/左/下/右坐标在移动到它们之前有效。因此,它确保字符是一个“u”或“E”,并且不超出范围
# 1 楼答案
这是我想出的BFS搜索解决方案。 它将起点标记为“1”,然后将它可以到达的每个相邻点标记为“2”,将可以到达的每个相邻点标记为“3”,依此类推
然后从末尾开始,使用递减的“level”值向后移动,从而得到最短路径
spaceIsValid()只是确保空间不超出边界
# 2 楼答案
您的代码似乎执行了depth-first search(DFS)。要找到最短路径,您需要切换到breadth-first search(BFS)。这不是通过向现有代码中添加几个变量就能做到的。这需要重写你的算法
将DFS转换为BFS的一种方法是摆脱递归,转而使用显式的堆栈来跟踪到目前为止访问过的节点。在搜索循环的每次迭代中,你(1)从堆栈中弹出一个节点;(2) 检查该节点是否为解决方案;(3)将每个子对象推到堆栈上。在伪代码中,这看起来像:
深度优先搜索
如果随后将堆栈切换到队列,这将隐式成为BFS,BFS自然会找到最短路径
宽度优先的serarch
还有几点需要注意:
上述算法适用于树:没有回路的迷宫。如果你的迷宫有回路,那么你需要确保你不会重访你已经看到的节点。在这种情况下,需要添加逻辑来跟踪所有已访问的节点,并避免再次将它们添加到堆栈/队列中
如前所述,这些算法将找到目标节点,但它们不记得到达目标节点的路径。补充说,这对读者来说是一个练习