使用递归算法在迷宫中找到最短路径
Find Shortest Path in a Maze with Recursive Algorithm
我做了一个小的递归算法来找到以下格式的迷宫解决方案
###S###
##___##
##_#_##
#__#_##
#E___##
其中“#”代表一堵墙,“_”代表开放 space(可以自由穿过)。 '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;
}
但我无法将 mazeArray 设置为它可能找到的任何最短路径的正确值。
任何指导将不胜感激:)谢谢
spaceIsFree() 方法只是确保 up/left/down/right 坐标在移动到它们之前有效。所以它确保 char 是 '_' 或 'E' 并且它没有超出范围。
您的代码似乎在执行 depth-first search (DFS). To find the shortest path you will want to switch to a breadth-first search (BFS)。这不是您可以通过向现有代码添加一些变量来完成的事情。这将需要重写您的算法。
将 DFS 转换为 BFS 的一种方法是摆脱递归并切换到使用显式 堆栈 来跟踪您到目前为止访问过的节点.搜索循环的每次迭代,您 (1) 从堆栈中弹出一个节点; (2) 检查该节点是否为解; (3) 将其每个 children 压入堆栈。在伪代码中,它看起来像:
Depth-first 搜索
stack.push(startNode)
while not stack.isEmpty:
node = stack.pop()
if node is solution:
return
else:
stack.pushAll(node.children)
如果您随后将堆栈切换到 队列,这将隐式成为 BFS,并且 BFS 自然会找到最短路径。
Breadth-first 搜索
queue.add(startNode)
while not queue.isEmpty:
node = queue.remove()
if node is solution:
return
else:
queue.addAll(node.children)
一些补充说明:
以上算法适用于树:没有回路的迷宫。如果您的迷宫有循环,那么您需要确保您不会重新访问已经看过的节点。在这种情况下,您需要添加逻辑来跟踪所有已经访问过的节点,并避免将它们再次添加到 stack/queue。
正如所写,这些算法将找到目标节点,但它们不记得将它们带到那里的路径。添加这是 reader.
的练习
这是我提出的 BFS 搜索解决方案。
它将起点标记为“1”,然后将它可以移动到的每个相邻标记标记为“2”,将可以移动到的每个相邻标记为“3”,依此类推。
然后它从末尾开始,并使用递减的 "level" 值向后移动,从而得到最短路径。
private LinkedList<Point> findShortestPath(Point startLocation) {
// This double array keeps track of the "level" of each node.
// The level increments, starting at the startLocation to represent the path
int[][] levelArray = new int[mazeArray.length][mazeArray[0].length];
// Assign every free space as 0, every wall as -1
for (int i=0; i < mazeArray.length; i++)
for (int j=0; j< mazeArray[0].length; j++) {
if (mazeArray[i][j] == Maze.SPACE_CHAR || mazeArray[i][j] == Maze.END_CHAR)
levelArray[i][j] = 0;
else
levelArray[i][j] = -1;
}
// Keep track of the traversal in a queue
LinkedList<Point> queue = new LinkedList<Point>();
queue.add(startLocation);
// Mark starting point as 1
levelArray[startLocation.x][startLocation.y] = 1;
// Mark every adjacent open node with a numerical level value
while (!queue.isEmpty()) {
Point point = queue.poll();
// Reached the end
if (point.equals(maze.getEndCoords()))
break;
int level = levelArray[point.x][point.y];
ArrayList<Point> possibleMoves = new ArrayList<Point>();
// Move Up
possibleMoves.add(new Point(point.x, point.y + 1));
// Move Left
possibleMoves.add(new Point(point.x - 1, point.y));
// Down Move
possibleMoves.add(new Point(point.x, point.y - 1));
// Move Right
possibleMoves.add(new Point(point.x + 1, point.y));
for (Point potentialMove: possibleMoves) {
if (spaceIsValid(potentialMove)) {
// Able to move here if it is labeled as 0
if (levelArray[potentialMove.x][potentialMove.y] == 0) {
queue.add(potentialMove);
// Set this adjacent node as level + 1
levelArray[potentialMove.x][potentialMove.y] = level + 1;
}
}
}
}
// Couldn't find solution
if (levelArray[maze.getEndCoords().x][maze.getEndCoords().y] == 0)
return null;
LinkedList<Point> shortestPath = new LinkedList<Point>();
Point pointToAdd = maze.getEndCoords();
while (!pointToAdd.equals(startLocation)) {
shortestPath.push(pointToAdd);
int level = levelArray[pointToAdd.x][pointToAdd.y];
ArrayList<Point> possibleMoves = new ArrayList<Point>();
// Move Right
possibleMoves.add(new Point(pointToAdd.x + 1, pointToAdd.y));
// Down Move
possibleMoves.add(new Point(pointToAdd.x, pointToAdd.y - 1));
// Move Left
possibleMoves.add(new Point(pointToAdd.x - 1, pointToAdd.y));
// Move Up
possibleMoves.add(new Point(pointToAdd.x, pointToAdd.y + 1));
for (Point potentialMove: possibleMoves) {
if (spaceIsValid(potentialMove)) {
// The shortest level will always be level - 1, from this current node.
// Longer paths will have higher levels.
if (levelArray[potentialMove.x][potentialMove.y] == level - 1) {
pointToAdd = potentialMove;
break;
}
}
}
}
return shortestPath;
}
spaceIsValid() 只是确保 space 没有越界。
我做了一个小的递归算法来找到以下格式的迷宫解决方案
###S###
##___##
##_#_##
#__#_##
#E___##
其中“#”代表一堵墙,“_”代表开放 space(可以自由穿过)。 '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;
}
但我无法将 mazeArray 设置为它可能找到的任何最短路径的正确值。
任何指导将不胜感激:)谢谢
spaceIsFree() 方法只是确保 up/left/down/right 坐标在移动到它们之前有效。所以它确保 char 是 '_' 或 'E' 并且它没有超出范围。
您的代码似乎在执行 depth-first search (DFS). To find the shortest path you will want to switch to a breadth-first search (BFS)。这不是您可以通过向现有代码添加一些变量来完成的事情。这将需要重写您的算法。
将 DFS 转换为 BFS 的一种方法是摆脱递归并切换到使用显式 堆栈 来跟踪您到目前为止访问过的节点.搜索循环的每次迭代,您 (1) 从堆栈中弹出一个节点; (2) 检查该节点是否为解; (3) 将其每个 children 压入堆栈。在伪代码中,它看起来像:
Depth-first 搜索
stack.push(startNode)
while not stack.isEmpty:
node = stack.pop()
if node is solution:
return
else:
stack.pushAll(node.children)
如果您随后将堆栈切换到 队列,这将隐式成为 BFS,并且 BFS 自然会找到最短路径。
Breadth-first 搜索
queue.add(startNode)
while not queue.isEmpty:
node = queue.remove()
if node is solution:
return
else:
queue.addAll(node.children)
一些补充说明:
以上算法适用于树:没有回路的迷宫。如果您的迷宫有循环,那么您需要确保您不会重新访问已经看过的节点。在这种情况下,您需要添加逻辑来跟踪所有已经访问过的节点,并避免将它们再次添加到 stack/queue。
正如所写,这些算法将找到目标节点,但它们不记得将它们带到那里的路径。添加这是 reader.
的练习
这是我提出的 BFS 搜索解决方案。 它将起点标记为“1”,然后将它可以移动到的每个相邻标记标记为“2”,将可以移动到的每个相邻标记为“3”,依此类推。
然后它从末尾开始,并使用递减的 "level" 值向后移动,从而得到最短路径。
private LinkedList<Point> findShortestPath(Point startLocation) {
// This double array keeps track of the "level" of each node.
// The level increments, starting at the startLocation to represent the path
int[][] levelArray = new int[mazeArray.length][mazeArray[0].length];
// Assign every free space as 0, every wall as -1
for (int i=0; i < mazeArray.length; i++)
for (int j=0; j< mazeArray[0].length; j++) {
if (mazeArray[i][j] == Maze.SPACE_CHAR || mazeArray[i][j] == Maze.END_CHAR)
levelArray[i][j] = 0;
else
levelArray[i][j] = -1;
}
// Keep track of the traversal in a queue
LinkedList<Point> queue = new LinkedList<Point>();
queue.add(startLocation);
// Mark starting point as 1
levelArray[startLocation.x][startLocation.y] = 1;
// Mark every adjacent open node with a numerical level value
while (!queue.isEmpty()) {
Point point = queue.poll();
// Reached the end
if (point.equals(maze.getEndCoords()))
break;
int level = levelArray[point.x][point.y];
ArrayList<Point> possibleMoves = new ArrayList<Point>();
// Move Up
possibleMoves.add(new Point(point.x, point.y + 1));
// Move Left
possibleMoves.add(new Point(point.x - 1, point.y));
// Down Move
possibleMoves.add(new Point(point.x, point.y - 1));
// Move Right
possibleMoves.add(new Point(point.x + 1, point.y));
for (Point potentialMove: possibleMoves) {
if (spaceIsValid(potentialMove)) {
// Able to move here if it is labeled as 0
if (levelArray[potentialMove.x][potentialMove.y] == 0) {
queue.add(potentialMove);
// Set this adjacent node as level + 1
levelArray[potentialMove.x][potentialMove.y] = level + 1;
}
}
}
}
// Couldn't find solution
if (levelArray[maze.getEndCoords().x][maze.getEndCoords().y] == 0)
return null;
LinkedList<Point> shortestPath = new LinkedList<Point>();
Point pointToAdd = maze.getEndCoords();
while (!pointToAdd.equals(startLocation)) {
shortestPath.push(pointToAdd);
int level = levelArray[pointToAdd.x][pointToAdd.y];
ArrayList<Point> possibleMoves = new ArrayList<Point>();
// Move Right
possibleMoves.add(new Point(pointToAdd.x + 1, pointToAdd.y));
// Down Move
possibleMoves.add(new Point(pointToAdd.x, pointToAdd.y - 1));
// Move Left
possibleMoves.add(new Point(pointToAdd.x - 1, pointToAdd.y));
// Move Up
possibleMoves.add(new Point(pointToAdd.x, pointToAdd.y + 1));
for (Point potentialMove: possibleMoves) {
if (spaceIsValid(potentialMove)) {
// The shortest level will always be level - 1, from this current node.
// Longer paths will have higher levels.
if (levelArray[potentialMove.x][potentialMove.y] == level - 1) {
pointToAdd = potentialMove;
break;
}
}
}
}
return shortestPath;
}
spaceIsValid() 只是确保 space 没有越界。