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

Find Shortest Path in a Maze with Recursive Algorithm

提问by bbedward

I made a little recursive algorithm to find a solution to a maze in the following format

我做了一个小的递归算法来找到以下格式的迷宫的解决方案

###S###
##___##
##_#_##
#__#_##
#E___##

Where a '#' represents a wall, and '_' represents an open space (free to move through). 'S' represents the start location, 'E' represents the end location.

其中“#”代表一堵墙，“_”代表一个开放空间（可以自由穿过）。“S”代表开始位置，“E”代表结束位置。

My algorithm works fine, but I'm wondering how to modify it to work for the shortest path.

我的算法工作正常，但我想知道如何修改它以适用于最短路径。

/**
 * 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;
}

In the first block is where I find the path and break it out. The char[][] array with the path written on it is set as well, which is later printed out as the result.

在第一个块中，我找到了路径并将其分解。其上写有路径的 char[][] 数组也被设置，稍后将其作为结果打印出来。

It works well, but I'm wondering what would be the best way to modify it to not break out after it finds the first successful path, but keep going until it finds the shortest possible path.

它运作良好，但我想知道修改它的最佳方法是在找到第一个成功路径后不爆发，而是继续前进，直到找到最短的可能路径。

I tried doing something like this, modifying the findPath() method and adding a shortestPath and hasFoundPath variable. The first indicating length of the shortest path found so far, and the hasFoundPath variable indicating whether or not we have found any path.

我尝试做这样的事情，修改 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;
    }

But I haven't been able to get it to set the mazeArray to the correct values of any shortest path it may find.

但是我无法让它将 mazeArray 设置为它可能找到的任何最短路径的正确值。

Any guidance would be appreciated :) Thanks

任何指导将不胜感激:) 谢谢

spaceIsFree() method simply makes sure the up/left/down/right coordinates are valid before moving to them. So it makes sure the char is an '_' or 'E' and it isn't out of bounds.

spaceIsFree() 方法只是在移动到它们之前确保上/左/下/右坐标有效。所以它确保字符是'_'或'E'并且它没有越界。

回答by John Kugelman

Your code appears to perform a depth-first search(DFS). To find the shortest path you will want to switch to a breadth-first search(BFS). It's not something you can do by adding a few variables to your existing code. It will require rewriting your algorithm.

您的代码似乎执行深度优先搜索(DFS)。要找到最短路径，您需要切换到广度优先搜索(BFS)。通过向现有代码添加一些变量，您无法做到这一点。这将需要重写您的算法。

One way to convert a DFS into a BFS is to get rid of the recursion and switch to using an explicit stackto keep track of which nodes you've visited so far. Each iteration of your search loop, you (1) pop a node off the stack; (2) check if that node is the solution; and (3) push each of its children onto the stack. In pseudo code, that looks like:

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

Depth-first search

深度优先搜索

stack.push(startNode)

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

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

If you then switch the stack to a queuethis will implicitly become a BFS, and a BFS will naturally find the shortest path(s).

如果然后将堆栈切换到队列，这将隐式成为 BFS，并且 BFS 自然会找到最短路径。

Breadth-first serarch

广度优先搜索

queue.add(startNode)

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

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

A couple of additional notes:

一些额外的注意事项：

1. The above algorithms are suitable for trees: mazes that don't have loops. If your mazes have loops then you'll need to make sure you don't revisit nodes you've already seen. In that case, you'll need to add logic to keep track of all the already visited nodes and avoid adding them onto the stack/queue a second time.

2. As written, these algorithms will find the target node but they don't remember the path that got them there. Adding that is an exercise for the reader.

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

2. 正如所写，这些算法将找到目标节点，但它们不记得将它们带到那里的路径。添加这是读者的练习。

回答by bbedward

Here's the BFS-search solution I came up with. It marks the starting point as "1", then marks each adjacent one that it can travel to as "2", and each adjacent one to the 2's that can be traveled to as "3" and so on.

这是我想出的 BFS-search 解决方案。它将起点标记为“1”，然后将每个可以到达的相邻点标记为“2”，将可以到达的 2 的每个相邻点标记为“3”，依此类推。

Then it starts at the end, and goes backwards using the decrementing "level" values which results in the shortest path.

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

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;
}

The spaceIsValid() is simply ensuring that the space is not out of bounds.

spaceIsValid() 只是确保空间没有越界。