使用递归算法在迷宫中找到最短路径

Question

我写了一个小的递归算法，用于解决以下格式迷宫问题。

###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变量。shortestPath表示迄今为止找到的最短路径长度，而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()方法只是在移动之前确保上/左/下/右坐标有效。所以它确保字符是'_'或'E'，并且没有越界。

- bbedward

---

它必须是一个递归算法吗？Dijkstra算法的重要方面之一是共享内存，在递归的上下文中更难实现。 - Willem Van Onsem

不需要，只是我最初实现它时使用的简单算法。 - bbedward

Answer 1

你的代码似乎执行了深度优先搜索（DFS）。要找到最短路径，您需要切换到广度优先搜索（BFS）。这不是通过向现有代码添加几个变量就能完成的。它需要重写算法。

将DFS转换为BFS的一种方法是摆脱递归并切换到使用显式堆栈来跟踪迄今为止访问过的节点。在每次搜索循环中，您(1)从堆栈中弹出一个节点；(2)检查该节点是否为解决方案; (3)将其每个子节点压入堆栈。用伪代码表示如下：

stack.push(startNode)

while not stack.isEmpty:
    node = stack.pop()

    if node is solution:
        return
    else:
        stack.pushAll(node.children)

如果您将堆栈切换为 队列，则这将隐式地变成 BFS，并且 BFS 自然会找到最短路径。 广度优先搜索

queue.add(startNode)

while not queue.isEmpty:
    node = queue.remove()

    if node is solution:
        return
    else:
        queue.addAll(node.children)

还有一些额外的注释：

1. 上述算法适用于树形结构的迷宫，即没有循环的迷宫。如果你的迷宫中有循环，那么你需要确保不要重复访问已经访问过的节点。在这种情况下，你需要添加逻辑来跟踪所有已经访问过的节点，并避免第二次将它们添加到堆栈/队列中。

2. 如上所述，这些算法可以找到目标节点，但它们不会记住到达目标节点的路径。如何实现这一点是读者的练习。

- John Kugelman

---

谢谢，我会重新设计算法并在完成后发布 :) - bbedward

Answer 2

这是我想出的 BFS 搜索解决方案。 它将起点标记为“1”，然后将可以到达的每个相邻点标记为“2”，将可以到达 2 的每个相邻点标记为“3”等等。

然后从终点开始，使用递减的“级别”值向后移动，从而得到最短路径。

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()函数的作用是确保空间不超出边界。

- bbedward