这个迷宫算法如何return正确找到最短路径？

Question

我遇到了这个迷宫求解器算法：

public class Maze {

    public static void main(String[] args) {
        char[][] maze = {
                {'.', '.', '.', '0', '0', '0', '0', '0', '0', '0'},
                {'0', '0', '.', '.', '.', '0', '.', '.', '.', '0'},
                {'0', '0', '.', '0', '.', '0', '.', '0', '.', '0'},
                {'.', '.', '.', '0', '.', '0', '.', '0', '.', '0'},
                {'.', '0', '0', '0', '.', '.', '.', '0', '.', '0'},
                {'.', '.', '.', '.', '0', '0', '0', '.', '.', '0'},
                {'.', '0', '0', '.', '.', '.', '0', '.', '.', '0'},
                {'.', '.', '.', '0', '0', '.', '0', '0', '.', '.'},
                {'0', '0', '.', '0', '0', '.', '.', '.', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0', '.', '.', '.'},
        };

        print(maze);

        if(traverse(maze, 0, 0)) {
            System.out.println("SOLVED maze");
        } else {
            System.out.println("could NOT SOLVE maze");
        }

        print(maze);
    }

    private static void print(char[][] maze) {
        System.out.println("-----------------------");
        for(int x = 0; x < 10; x++) {
            System.out.print("| ");
            for(int y = 0; y < 10; y++) {
                System.out.print(maze[x][y] + " ");
            }
            System.out.println("|");
        }
        System.out.println("-----------------------");
    }

    public static boolean isValidSpot(char[][] maze, int r, int c) {
        if(r >= 0 && r < 10 && c >= 0 && c < 10) {
            return maze[r][c] == '.';
        }
        return false;
    }

    public static boolean traverse(char[][] maze, int r, int c) {
        if(isValidSpot(maze, r, c)) {
            //it is a valid spot
            if(r == 9 && c == 9) {
                return true;
            }

            maze[r][c] = '*';

            //up
            boolean returnValue = traverse(maze, r - 1, c);


            //right
            if(!returnValue) {
                returnValue = traverse(maze, r, c + 1);
            }

            //down
            if(!returnValue) {
                returnValue = traverse(maze, r + 1, c);
            }

            //left
            if(!returnValue) {
                returnValue = traverse(maze, r, c - 1);
            }

            if(returnValue) {
                System.out.println(r + ", " + c);
                maze[r][c] = ' ';
            }
            return returnValue;
        }

        return false;
    }
}

但我无法在脑海中计算出递归。即使算法在搜索出口点时遇到了死胡同，并将它通过的路径标记为无效，无法通过，它也会以某种方式 returns 到达最后一个检查点，同时不会打印死胡同路径。这是最让我困惑的部分。此算法中如何不打印死胡同路径？

我尝试在每一步都打印迷宫，但仍然无法弄清楚如何不打印无效路径。

Answer 1

该函数实现深度优先搜索，也称为DFS寻找路径。您可以阅读更多关于 DFS 和 BFS here 的内容。大致情况如下：

检查当前坐标是否为结束坐标，如果为returns True
否则，检查是否可以向上推进到达终点

2.1如果向上推进可以到达终点，打印这个坐标，然后returnTrue
否则，向右前进看看能不能走到尽头

3.1如果向上前进能到达终点，打印这个坐标，然后returnTrue
否则，检查是否可以向下前进到达终点

4.1如果向上前进能到达终点，打印这个坐标，然后returnTrue
否则，检查是否可以向左前进

5.1如果向上推进可以到达终点，打印这个坐标，然后returnTrue
否则，returnFalse，意思是从这个坐标你不能到达终点

不是保留要访问的状态列表，而是将信息存储在递归中。

迷宫中路径的 DFS 搜索的类似问题可以在中找到，在 Python 中实现并且可能更容易理解这个概念，因为它不是用递归实现的，而是用一个列表。

请注意所写的算法并没有找到最短路径，而是找到了a路径。要找到最短路径，您应该使用 BFS，因为它会在检查具有 x+1 步的路径之前用 x 步覆盖所有路径。

Answer 2

深度优先搜索不是寻找最短路径的最佳选择。广度优先搜索可确保您在找到解决方案（路径）时处于最短路径。

BFS需要标记已经搜索到的位置（如代码中的'*'），当前路径长度。并保留刚刚到达的位置列表：边界。

下一步从边界看新的邻居，这将形成新的边界。目标应该是邻居（(r == 9 && c == 9)）。

边界最初是起点：{(0, 0)}。边界点的数量最初会增加，然后随着 dead-ends 被删除而再次减少。固定大小的数组很复杂，因此 Set 或 List 更合适。

真正的递归 BFS 更容易，但你可能会遍历边界，并且通过留下“面包屑”重建最短路径。

对于一个位置 record class 是最简单的。由于 Java 16.

record Location (int row, int column) {
    List<Location> getNeighbors() {
        List<Location> nbs = new ArrayList<>();            
        if (row > 0) {
            nbs.add(new Location(row - 1, column));
        }
        if (row < 10-1) {
            nbs.add(new Location(row + 1, column));
        }
        if (column > 0) {
            nbs.add(new Location(row, column - 1));
        }
        if (column < 10-1) {
            nbs.add(new Location(row, column + 1));
        }
        return nbs;
    }

}

对于边界，一组更合适，因为从两个旧边界位置可以到达相同的新边界位置。

Set<Location> border = new HashSet<>();
border.add(new Location(0, 0));
int pathLength = 0;

void moveToNextBorder(Set<Location> border) {
    char breadCrumb = 'a' + pathLength;
    ++pathLength;
    Set<Location> result = new HashSet<>();
    for (Location oldLoc: border) {
        maze[oldLoc.row][oldLoc.column] = breadCrumb;
    }
    for (Location oldLoc: border) {
        for (Location loc: oldLoc.getNeighbors()) {
            if (maze[loc.row][loc.column] == '.') {
                result.add(loc); // Could already have been added.
            }
        }
    }
    border.clear();
    border.addAll(result);
}

查看新边框是否到达目标：

moveToNextBorder(border);
if (border.contains(new Location(9, 9))) {
    // Take a shortest path, using breadCrumbs downto 'a'.
    Location[] shortestPath = new Location[pathLength];
    ...
}

这个迷宫算法如何return正确找到最短路径？

How does this maze algorithm return the shortest path correctly?

java

algorithm

recursion

maze