英文:
Breadth-First Search takes way too long to solve maze
问题
我有一个大的、开放式的迷宫，像这样：
############################################################
#.....................#...#................#.........#.....#
#..##.......x.........#.#.#...#.........x..#......#..#.....#
#...#.......#....#....#.#.#...#...####.....####...#..#####.#
#.....###...#....#....###.#...#.........#.........#......#.#
####.#..#...#....#........#...#####..#..#...#######..##..#.#
#....##.....#....#................#..####......#...........#
#......##...######........x....................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#.....####...............#
#.....#...#..#..#..#......#.......#........................#
#.....#####..#..#..#......#.......######............x......#
#.........................#................................#
#..................x......#..##..........#####.............#
#.........................####.............................#
#..........................................................#
#....##.....#....#................#..####......#...........#
#.....s##...######.............................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#...x.####...............#
#.....#...#..#...x.#......#.......#.................#......#
#.....#####..#..#..#...#..###....#######............######.#
#...............#..x...#..#.....##...........####...#......#
#...............#......#.........#.........##...#..........#
#...............#......#.........#..........#............#.#
############################################################
"s"是起点。并且有多个目标点"x"。我只需要找到一个目标点。如果目标离起点很近，BFS算法可以很快找到解决方案。如果目标点像上面的例子一样距离较远，则需要很长时间。
所以我的问题是：
a）对于这种特定类型的迷宫，BFS算法是否不适用，我是否应该使用A*或类似的算法。
b）我的实现是否存在问题？
实现：
public class BFS {
public static String getPath(String[][] map) {
// 代码部分不翻译
}
private static boolean foundBait(String[][] map, String moves) {
// 代码部分不翻译
}
private static boolean valid(String[][] map, String moves) {
// 代码部分不翻译
}
}
英文:
I have an big, open maze like this:
############################################################
#.....................#...#................#.........#.....#
#..##.......x.........#.#.#...#.........x..#......#..#.....#
#...#.......#....#....#.#.#...#...####.....####...#..#####.#
#.....###...#....#....###.#...#.........#.........#......#.#
####.#..#...#....#........#...#####..#..#...#######..##..#.#
#....##.....#....#................#..####......#...........#
#......##...######........x....................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#.....####...............#
#.....#...#..#..#..#......#.......#........................#
#.....#####..#..#..#......#.......######............x......#
#.........................#................................#
#..................x......#..##..........#####.............#
#.........................####.............................#
#..........................................................#
#....##.....#....#................#..####......#...........#
#.....s##...######.............................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#...x.####...............#
#.....#...#..#...x.#......#.......#.................#......#
#.....#####..#..#..#...#..###....#######............######.#
#...............#..x...#..#.....##...........####...#......#
#...............#......#.........#.........##...#..........#
#...............#......#.........#..........#............#.#
############################################################
"s" is the starting point. And there are multiple destination points "x". I just need to find one destination. The BFS algorithm can find a solution pretty quick if a destination is close to the starting point. If they are further away like in the example above, it takes endless time.
So my questions are:
a) Is the algorithm bad for this specific type of maze and should I rather use A* or something like that.
b) Is my implementation bad?
Implementation:
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;
}
}
答案1
得分: 1
如评论中所述，问题在于没有标记添加到路径中的节点，解决方案是使用第二个矩阵进行标记。
英文:
As stated in the comments, problem was not marking the nodes added to the paths, and the solution is to use a second matrix for marking.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论