广度优先搜索在解决迷宫问题时耗时过长。

Question

我有一个大的、开放式的迷宫，像这样：

############################################################
#.....................#...#................#.........#.....#
#..##.......x.........#.#.#...#.........x..#......#..#.....#
#...#.......#....#....#.#.#...#...####.....####...#..#####.#
#.....###...#....#....###.#...#.........#.........#......#.#
####.#..#...#....#........#...#####..#..#...#######..##..#.#
#....##.....#....#................#..####......#...........#
#......##...######........x....................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#.....####...............#
#.....#...#..#..#..#......#.......#........................#
#.....#####..#..#..#......#.......######............x......#
#.........................#................................#
#..................x......#..##..........#####.............#
#.........................####.............................#
#..........................................................#
#....##.....#....#................#..####......#...........#
#.....s##...######.............................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#...x.####...............#
#.....#...#..#...x.#......#.......#.................#......#
#.....#####..#..#..#...#..###....#######............######.#
#...............#..x...#..#.....##...........####...#......#
#...............#......#.........#.........##...#..........#
#...............#......#.........#..........#............#.#
############################################################

"s"是起点，而有多个目标点"x"。我只需要找到一个目的地。如果目的地离起点很近，BFS算法可以很快地找到解决方案。但如果它们像上面的示例那样远，它将需要无尽的时间。 所以我的问题是： a）这种特定类型的迷宫是否不适合该算法，我应该使用A*或类似的算法。 b）我的实现方法是否不好。

实施：

public class BFS {

    public static String getPath(String[][] map) {
        String[] ways = { "L", "R", "U", "D" }; // directions to go
        Queue<String> q = new LinkedList<>();
        q.offer("");
        String path = "";

        while (!foundBait(map, path)) {
            path = q.poll();

            for (String s : ways) {
                String newPath = path + s;
                if (valid(map, newPath))
                    q.offer(newPath);
            }
        }
        return path;
    }

    private static boolean foundBait(String[][] map, String moves) {
        int xStart = 0;
        int yStart = 0;

        for (int y = 0; y < map.length; y++)
            for (int x = 0; x < map[0].length; x++)
                if (map[y][x].equals("s")) {
                    xStart = x;
                    yStart = y;
                }

        int i = xStart;
        int j = yStart;

        for (int s = 0; s < moves.length(); s++) {

            if (moves.charAt(s) == "L".charAt(0))
                i--;
            else if (moves.charAt(s) == "R".charAt(0))
                i++;
            else if (moves.charAt(s) == "U".charAt(0))
                j--;
            else if (moves.charAt(s) == "D".charAt(0))
                j++;

        }

        if (map[j][i].equals("x"))
            return true;

        return false;
    }

    private static boolean valid(String[][] map, String moves) {
        int xStart = 0;
        int yStart = 0;

        for (int y = 0; y < map.length; y++)
            for (int x = 0; x < map[0].length; x++)
                if (map[y][x].equals("s")) {
                    xStart = x;
                    yStart = y;
                }

        int i = xStart;
        int j = yStart;

        for (int s = 0; s < moves.length(); s++) {

            if (moves.charAt(s) == "L".charAt(0))
                i--;
            else if (moves.charAt(s) == "R".charAt(0))
                i++;
            else if (moves.charAt(s) == "U".charAt(0))
                j--;
            else if (moves.charAt(s) == "D".charAt(0))
                j++;

            if (!(0 <= i && i < map[0].length && 0 <= j && j < map.length))
                return false;
            else if (map[j][i].equals("#") || map[j][i].equals("-"))
                return false;

        }
        return true;
    }

}

- Ibrahim

---

你尝试过调试你的代码吗？在我看来，你在算法实现中犯了一个错误。地图只有30x30，对于现代计算机来说并不算太大，不应该花费太长时间。 - Amongalen

BFS不适用于这种问题，因为它是一种遍历算法。如果你想要找到两点之间的最短路径，例如，你可以使用Dijkstra算法。 - Vladimir Stanciu

自从我深入研究 A* 或 Dijkstra 算法以来已经过去了多年，但如果我的记忆没有出错的话，它们确实对于沿着图空间遍历的代价不同的情况非常有效。换句话说，它可以在许多路径中找到“最短路径”，但我认为您的标准并不是这样。如果您只是想寻找“任何一个”路径到“任何一个” x，我认为 BFS 是解决方法。 - spartygw

@Vladimir 他不想找最短路径。他想找到任何x的路径。这是一个不同的问题。当移动1个网格空间的所有成本相同时，Dijkstra本质上是BFS。 - spartygw

你可以在这里找到一个例子：https://www.baeldung.com/java-breadth-first-search。在你的情况下，你可以创建第二个矩阵来标记已访问的位置，或者创建一个整数集合，其中每个整数是矩阵中展开的位置。例如，map[1][1]将被设置为set[1*n +1]，其中n是您的矩阵列数。因此，map[i][j] -> set[i*n + j]。 - Vladimir Stanciu

Answer 1

正如评论中所述，问题在于没有标记添加到路径中的节点，解决方案是使用第二个矩阵进行标记。

- Vladimir Stanciu