#java #breadth-first-search #path-finding #maze
#java #поиск в ширину #поиск пути #Лабиринт
Вопрос:
У меня есть большой открытый лабиринт, подобный этому:
############################################################
#.....................#...#................#.........#.....#
#..##.......x.........#.#.#...#.........x..#......#..#.....#
#...#.......#....#....#.#.#...#...####.....####...#..#####.#
#.....###...#....#....###.#...#.........#.........#......#.#
####.#..#...#....#........#...#####..#..#...#######..##..#.#
#....##.....#....#................#..####......#...........#
#......##...######........x....................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#.....####...............#
#.....#...#..#..#..#......#.......#........................#
#.....#####..#..#..#......#.......######............x......#
#.........................#................................#
#..................x......#..##..........#####.............#
#.........................####.............................#
#..........................................................#
#....##.....#....#................#..####......#...........#
#.....s##...######.............................#......######
#....##........................................#...........#
#.........##########...############........#...#...####....#
#.....#...#..#..#..#......#.......#........#...#....###....#
#######...#..#..#..#......#.......#...x.####...............#
#.....#...#..#...x.#......#.......#.................#......#
#.....#####..#..#..#...#..###....#######............######.#
#...............#..x...#..#.....##...........####...#......#
#...............#......#.........#.........##...#..........#
#...............#......#.........#..........#............#.#
############################################################
«s» — это отправная точка. И есть несколько точек назначения «x». Мне просто нужно найти одно место назначения. Алгоритм BFS может найти решение довольно быстро, если пункт назначения находится близко к начальной точке. Если они находятся дальше, как в примере выше, это занимает бесконечное время.
Итак, мои вопросы:
a) Является ли алгоритм плохим для этого конкретного типа лабиринта, и я должен использовать A * или что-то в этом роде.
б) Плохая ли моя реализация?
Реализация:
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 amp;amp; i < map[0].length amp;amp; 0 <= j amp;amp; j < map.length))
return false;
else if (map[j][i].equals("#") || map[j][i].equals("-"))
return false;
}
return true;
}
}
Комментарии:
1. Вы пробовали отлаживать свой код? Мне кажется, что вы где-то допустили ошибку в своей реализации алгоритма. Это не должно занять слишком много времени, ваша карта размером всего 30×30, это не так много для современных компьютеров.
2. BFS не подходит для такой проблемы, потому что это алгоритм обхода. Если вы хотите найти кратчайший путь между 2 точками, вы могли бы использовать алгоритм Дейкстры, например.
3. Прошло много лет с тех пор, как я углубился в A * или Дейкстру, но, если память не изменяет, они действительно эффективны там, где затраты на прохождение по графическому пространству варьируются. Другими словами, он может найти «кратчайший путь» среди многих путей, но я не думаю, что ваши критерии таковы. Если вы просто ищете «любой» путь к «любому» x, я думаю, что BFS — это способ сделать это.
4. @Vladimir он не хочет находить кратчайший путь. Он хочет найти «любой» путь к любой x. Другая проблема. Дейкстра по сути является BFS, когда все затраты на перемещение 1 ячейки сетки одинаковы.
5. У вас есть пример здесь: baeldung.com/java-breadth-first-search . В вашем случае вы могли бы либо создать вторую матрицу, в которой вы отмечаете посещенные позиции, либо набор целых чисел, где каждое целое число является сглаженной позицией в вашей матрице. Например, map [1] [1] будет установлен [1 * n 1], где n — количество столбцов вашей матрицы. Итак, map [i][j] -> set [i * n j]
Ответ №1:
Как указано в комментариях, проблема заключалась в том, что не были отмечены узлы, добавленные к путям, и решение заключается в использовании второй матрицы для маркировки.