AI: Самый быстрый алгоритм, чтобы найти, если путь существует?
Я ищу алгоритм нахождения пути для ИИ, управляющего объектом в 2D-сетке, который должен найти путь от A до B. Он не должен быть кратчайшим, но его нужно вычислять очень быстро. Сетка является статической (никогда не изменяется), и некоторые ячейки сетки заняты препятствиями.
В настоящее время я использую A*, но он слишком медленный для моих целей, потому что он всегда пытается вычислить самый быстрый путь. Основная проблема производительности возникает, когда путь не существует, и в этом случае A* попытается исследовать слишком много ячеек.
Есть ли другой алгоритм, который я мог бы использовать, который мог бы найти путь быстрее, чем A*, если путь не должен быть кратчайшим?
Спасибо,
люминал
7 ответов
Предполагая, что ваша сетка статична и не меняется. Вы можете рассчитать связанные компоненты вашего графика один раз после построения сетки.
Затем вы можете легко проверить, находятся ли исходная и целевая вершины в компоненте или нет. Если да, то выполните A*, если нет, то не выполняйте, поскольку между компонентами не может быть пути.
Вы можете получить связанные компоненты графика, используя BFS или DFS.
Чтобы найти путь вместо кратчайшего, используйте любой обход графа (например, сначала в глубину, либо в первую очередь). Он не обязательно будет быстрее, на самом деле он может проверять намного больше узлов, чем A* на некоторых графиках, поэтому это зависит от ваших данных. Однако это будет легче реализовать, а постоянные факторы будут значительно ниже.
Чтобы избежать поиска пути, когда его нет, вы можете создать непересекающиеся множества (один раз после построения графика), чтобы очень быстро проверить, связаны ли две заданные точки. Для построения требуются линейное пространство и линейное время, а для поиска требуется амортизированное практически постоянное время, но вам все равно нужно время от времени запускать полный алгоритм, поскольку он только скажет вам , есть ли путь, а не куда он идет.
Если вы уже строите структуры данных заранее и у вас есть немного больше времени и пространства для обмена на мгновенные кратчайшие пути во время выполнения, вы можете получить свой торт и съесть его тоже: алгоритм Флойда-Варшалла дает вам все кратчайшие пути в сравнительно скромный O(|V|^3) время, которое является самым лучшим для доллара, учитывая, что есть пары |V|² (начало, место назначения). Вычисляет |V| * |V| матрица, которая может быть немного большой, но учтите, что это целочисленная матрица, и вам нужно только |V| * |V| * log_2 |V| биты (например, это 1,25 МБ для 1024 вершин).
Вы можете использовать DFS или BFS, так как вы просто хотите знать, связаны ли две вершины. Оба алгоритма работают в O(|V|) где V это множество всех вершин в графе.
Используйте любой из этих двух алгоритмов, если ваша эвристика занимает некоторое нетривиальное время для вычисления, в противном случае я думаю, что A* должен работать аналогично или лучше, чем DFS или BFS.
В качестве другого варианта вы можете использовать алгоритм Флойда-Варшалла (O(V^3)) вычислить, после создания сетки, путь наименьшего расстояния между каждой парой вершин, выполнив таким образом всю тяжелую работу в начале моделирования, а затем сохранив все кратчайшие пути для доступа O(1) в хэше, или если это оказывается слишком взрывоопасным для памяти, вы можете просто сохранить матрицу next такой, что next[i][j] хранит вершину, которую мы должны взять, чтобы перейти от вершины i к вершине j, Таким образом, мы можем построить путь из i в jкак (i, k1=next[i][j]), (k1, k2=next[k1][j]) ... (kr, j)
Если график достаточно мал, вы можете предварительно вычислить все кратчайшие пути, используя алгоритм Флойда-Варшалла. Это занимает O(|V|²) память для хранения путей и O(|V|³) время для предварительного расчета.
Очевидно, что это не вариант для очень больших графиков. Для них вы должны использовать ответ Томаса и предварительно вычислить подключенные компоненты (занимает линейное время и память), чтобы избежать самых дорогих поисков A*.
A*, BFS, DFS и все другие алгоритмы поиска должны проверять одинаковое количество узлов, когда нет пути, поэтому "сначала использовать DFS" не является хорошим ответом. И использовать Floyd-Warshall совершенно не нужно.
Для статических графов решение простое; смотрите @ ответ Томаса. Для нестатических графов проблема более сложна; смотрите этот ответ для хорошего алгоритма.
Если ваш лабиринт никогда не меняется и какой-либо существующий путь существует вечно, не могли бы вы использовать алгоритм отображения, который бы находил "области" вашего лабиринта и сохранял их в каком-то формате? Использование памяти будет линейным с количеством узлов или ячеек, а скорость - это скорость доступа и сравнения двух элементов массива.
Вычисление (разделение на регионы), вероятно, займет больше времени, но это делается один раз в начале. Может быть, вы могли бы адаптировать какой-либо алгоритм заливки для этой цели?
Не уверен, если это ясно из вышесказанного, но я думаю, что пример всегда помогает. Я надеюсь, что вы простите меня, используя синтаксис PHP.
пример (лабиринт 5х5) ([] помечает препятствие):
0 1 2 3 4
+----------+
0 |[][] 2 |
1 | [][] |
2 | [] []|
3 | 1 [] |
4 | [] |
+----------+
проиндексированные регионы (лучше использовать числовой хеш вместо x:y):
$regions=array(
'0:1'=>1,'0:2'=>1,'0:3'=>1,'0:4'=>1,'1:2'=>1,'1:3'=>1,'1:4'=>1,
'2:0'=>2,'3:0'=>2,'3:1'=>2,'3:2'=>2,'3:3'=>2,'3:4'=>2,'4:0'=>2,
'4:1'=>2,'4:3'=>2,'4:4'=>2
);
тогда ваша задача состоит только в том, чтобы определить, находятся ли ваши начальная и конечная точки в одном регионе:
if ( $regions[$startPoint] == $regions[$endPoint] )
pathExists();
Теперь, если я не ошибаюсь, сложность (скорость) A* зависит от расстояния между начальной и конечной точками (или длины решения), и это может быть использовано для ускорения поиска.
Я бы попытался создать несколько "узловых узлов" (JN) в лабиринте. Они могут быть расположены в функции (чтобы быстро узнать, где находится ближайший JN), и вы будете иметь пути между всеми соседними JN, предварительно рассчитанными.
Таким образом, вам нужно только найти решение от начальной точки до ближайшего JN и от конечной точки до ближайшего JN (где все они находятся в одном регионе (см. Выше)). Теперь я могу видеть сценарий (если функция не была правильно выбрана в отношении сложности лабиринта), в котором есть несколько областей, в некоторых из которых может не быть JN вообще, или что все ваши JN падают на препятствия в лабиринте... Поэтому, возможно, было бы лучше вручную определить эти JN, если это возможно, или сделать эту функцию размещения JN нетривиальной (принимая во внимание площадь каждого региона).
Как только вы достигнете JN, пути между ними могут быть проиндексированы (для быстрого извлечения предварительно определенного пути между начальной и конечной JN) или выполнить другое нахождение A* пути, за исключением этого времени только для набора "узлов соединения" - так как их намного меньше из них этот путь поиска между JN будет быстрее.
Вы можете рассмотреть возможность использования алгоритма Anytime A* (ANA* или других вариантов).
Они начнутся с выполнения жадного поиска в первую очередь, чтобы найти начальный путь.
Затем он будет постепенно улучшать работу с эвристической функцией, которая становится все менее и менее взвешенной.
Вы можете прекратить поиск в любое время и найти лучший путь.