java广度优先搜索要花很长时间才能解决迷宫

6ovsh4lw  于 2021-07-05  发布在  Java
关注(0)|答案(1)|浏览(306)

我有一个很大的开放式迷宫,像这样:


############################################################ 

# .....................#...#................#.........#.....#

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

}
f5emj3cl

f5emj3cl1#

如注解中所述,问题不是标记添加到路径中的节点,解决方法是使用第二个矩阵进行标记。

相关问题