Найти путь - Pathfinding

Для использования в других целях см. Следопыт (значения).
График и дерево
алгоритмы поиска
Списки
похожие темы
Эквивалентные пути между A и B в 2D-среде

Найти путь или же путь это построение с помощью компьютерного приложения кратчайшего маршрута между двумя точками. Это более практичный вариант на решение лабиринтов. Эта область исследований во многом основана на Алгоритм Дейкстры для поиска кратчайшего пути на взвешенный график.

Поиск пути тесно связан с проблема кратчайшего пути, в теория графов, который исследует, как определить путь, который лучше всего соответствует некоторым критериям (самый короткий, самый дешевый, самый быстрый и т. д.) между двумя точками в большой сети.

Алгоритмы

По сути, метод поиска пути ищет график начиная с одного вершина и исследуя соседние узлы пока не будет достигнут узел назначения, как правило, с целью поиска самого дешевого маршрута. Хотя методы поиска по графам, такие как поиск в ширину найдет маршрут, если у него будет достаточно времени, другие методы, которые «исследуют» график, будут стремиться достичь пункта назначения раньше. Аналогия: человек, идущий по комнате; вместо того, чтобы заранее исследовать все возможные маршруты, человек обычно идет в направлении пункта назначения и отклоняется от пути только для того, чтобы избежать препятствия, и делать отклонения как можно более незначительными.

Две основные проблемы поиска пути: (1) найти путь между двумя узлами в график; и (2) проблема кратчайшего пути - найти оптимальный кратчайший путь. Базовые алгоритмы, такие как в ширину и в глубину поиск решить первую проблему по утомительный все возможности; начиная с данного узла, они перебирают все возможные пути, пока не достигнут конечного узла. Эти алгоритмы работают в , или линейное время, где V - количество вершин, а E - количество края между вершинами.

Более сложная проблема - найти оптимальный путь. Исчерпывающий подход в этом случае известен как Алгоритм Беллмана – Форда, что дает временную сложность , или квадратичное время. Однако необязательно перебирать все возможные пути, чтобы найти оптимальный. Такие алгоритмы, как А * и Алгоритм Дейкстры стратегически исключить пути, либо через эвристика или через динамическое программирование. За счет исключения невозможных путей эти алгоритмы могут достичь временной сложности до .[1]

Вышеупомянутые алгоритмы являются одними из лучших общих алгоритмов, которые работают с графом без предварительной обработки. Однако в практических системах маршрутизации путешествий даже лучшие временные сложности могут быть достигнуты с помощью алгоритмов, которые могут предварительно обрабатывать график для достижения лучшей производительности.[2] Один из таких алгоритмов иерархии сжатия.

Алгоритм Дейкстры

Типичный пример алгоритма поиска пути на основе графа: Алгоритм Дейкстры. Этот алгоритм начинается с начального узла и «открытого набора» узлов-кандидатов. На каждом шаге исследуется узел в открытом множестве с наименьшим расстоянием от старта. Узел помечается как «закрытый», и все соседние с ним узлы добавляются в открытый набор, если они еще не были исследованы. Этот процесс повторяется до тех пор, пока не будет найден путь к месту назначения. Поскольку в первую очередь проверяются узлы с наименьшим расстоянием, при первом обнаружении пункта назначения путь к нему будет кратчайшим.[3]

Алгоритм Дейкстры не работает, если есть отрицательный край масса. В гипотетической ситуации, когда узлы A, B и C образуют связный неориентированный граф с ребрами AB = 3, AC = 4 и BC = −2, оптимальный путь от A до C стоит 1, а оптимальный путь от A до B стоит 2. Алгоритм Дейкстры, начиная с A, сначала исследует B, так как он является ближайшим. Он присвоит ему стоимость 3 и пометит его закрытым, что означает, что его стоимость никогда не будет переоценена. Следовательно, метод Дейкстры не может оценивать отрицательные веса ребер. Однако, поскольку для многих практических целей отрицательного веса ребра никогда не будет, алгоритм Дейкстры в значительной степени подходит для целей поиска пути.

Алгоритм A *

А * - это вариант алгоритма Дейкстры, обычно используемый в играх. A * присваивает вес каждому открытому узлу, равному весу края этого узла плюс приблизительное расстояние между этим узлом и финишем. Это приблизительное расстояние определяется эвристический, и представляет собой минимально возможное расстояние между этим узлом и концом. Это позволяет исключить более длинные пути после нахождения исходного пути. Если между началом и концом есть путь длиной x, а минимальное расстояние между узлом и концом больше x, этот узел не нужно исследовать.[4]

A * использует эту эвристику для улучшения поведения по сравнению с алгоритмом Дейкстры. Когда эвристика дает нулевое значение, A * эквивалентен алгоритму Дейкстры. По мере того как эвристическая оценка увеличивается и приближается к истинному расстоянию, A * продолжает находить оптимальные пути, но работает быстрее (за счет проверки меньшего количества узлов). Когда значение эвристики точно соответствует истинному расстоянию, A * проверяет наименьшее количество узлов. (Однако, как правило, нецелесообразно писать эвристическую функцию, которая всегда вычисляет истинное расстояние, поскольку тот же результат сравнения часто можно получить с помощью более простых вычислений - например, с помощью Манхэттенское расстояние над Евклидово расстояние в двумерное пространство.) По мере увеличения значения эвристики A * проверяет меньше узлов, но больше не гарантирует оптимальный путь. Во многих приложениях (например, в видеоиграх) это приемлемо и даже желательно, чтобы алгоритм работал быстро.

Пример алгоритма

Это довольно простой и понятный алгоритм поиска пути для тайловых карт. Для начала у вас есть карта, координаты начала и координаты пункта назначения. Карта будет выглядеть так, Икс будучи стенами, S быть началом, О быть финишем и _ Поскольку это открытые пространства, цифры по верхнему и правому краям - это номера столбцов и строк:

  1 2 3 4 5 6 7 8X XXXXXXXX XX _ _ _ XX _ X _ X 1X _ X _ _ X _ _ _ X 2X SXX _ _ _ X _ X 3X _ X _ _ X _ _ _ X 4X _ _ _ XX _ X _ X 5X _ X _ _ X _ X _ X 6X _ XX _ _ _ X _ X 7X _ _ O _ X _ _ _ X 8X XXXXXXXXX

Сначала создайте список координат, который мы будем использовать в качестве очереди. Очередь будет инициализирована одной координатой, конечной координатой. К каждой координате также будет прикреплена переменная счетчика (цель этого скоро станет очевидной). Таким образом, очередь начинается как ((3,8,0)).

Затем просмотрите все элементы в очереди, включая элементы, добавленные в конец в ходе алгоритма, и для каждого элемента выполните следующие действия:

  1. Создайте список из четырех смежных ячеек с переменной счетчика переменной счетчика текущего элемента + 1 (в нашем примере четыре ячейки: ((2,8,1), (3,7,1), (4, 8,1), (3,9,1)))
  2. Проверьте все ячейки в каждом списке на следующие два условия:
    1. Если ячейка - стена, удалите ее из списка
    2. Если в основном списке есть элемент с такой же координатой и счетчиком больше или равно, удалите его из списка ячеек
  3. Добавить все оставшиеся ячейки списка в конец основного списка
  4. Перейти к следующему пункту в списке

Таким образом, после первого хода список элементов следующий: ((3,8,0), (2,8,1), (4,8,1))

  • После 2 ходов: ((3,8,0), (2,8,1), (4,8,1), (1,8,2), (4,7,2))
  • После 3 ходов: (... (1,7,3), (4,6,3), (5,7,3))
  • После 4 ходов: (... (1,6,4), (3,6,4), (6,7,4))
  • После 5 ходов: (... (1,5,5), (3,5,5), (6,6,5), (6,8,5))
  • После 6 ходов: (... (1,4,6), (2,5,6), (3,4,6), (6,5,6), (7,8,6))
  • После 7 ходов: (... (1,3,7)) - проблема решена, завершите этот этап алгоритма - обратите внимание, что если у вас есть несколько юнитов, преследующих одну и ту же цель (как во многих играх - подход от конца к началу алгоритм призван упростить эту задачу), вы можете продолжать, пока не будет занята вся карта, все отряды или не достигнут установленный предел счетчика

Теперь сопоставьте счетчики на карте, получив следующее:

  1 2 3 4 5 6 7 8X XXXXXXXX XX _ _ _ XX _ X _ X 1X _ X _ _ X _ _ _ X 2X SXX _ _ _ X _ X 3X 6 X 6 _ X _ _ _ X 4X 5 6 5 XX 6 X _ X 5X 4 X 4 3 X 5 X _ X 6X 3 XX 2 3 4 X _ X 7X 2 1 0 1 X 5 6 _ X 8X XXXXXXXXX

Теперь начните с S (7) и перейдите к ближайшей ячейке с наименьшим номером (непроверенные ячейки нельзя переместить). Прослеживаемый путь: (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> ( 1,8,2) -> (2,8,1) -> (3,8,0). В случае, если два числа одинаково малы (например, если S было в (2,5)), выберите случайное направление - длины одинаковы. Теперь алгоритм завершен.

В видеоиграх

Крис Кроуфорд в 1982 году описал, как он «потратил много времени», пытаясь решить проблему с поиском пути в Tanktics, в котором компьютерные танки застряли на суше в U-образных озерах. «После долгих усилий я нашел лучшее решение: удалить U-образные озера с карты», - сказал он.[5]

Иерархический поиск пути

Quadtrees может использоваться для поиска иерархического пути

Идея была впервые описана индустрия видеоигр, который требовал планирования на больших картах с небольшим количеством Время процессора. Концепция использования абстракции и эвристика старше и впервые упоминается под названием ABSTRIPS (Abstraction-Based Полоски )[6] который использовался для эффективного поиска пространств состояний логических игр.[7] Похожая техника навигационные сетки (navmesh), которые используются для геометрического планирования в играх и мультимодальных планирование транспортировки который используется в проблемы коммивояжера с более чем одним транспортным средством.

Карта разделена на кластеры. На высокоуровневом слое планируется путь между кластерами. После того, как план был найден, планируется второй путь в кластере на нижнем уровне.[8] Это означает, что планирование выполняется в два этапа, что является управляемый местный поиск в исходном пространстве. Преимущество состоит в том, что количество узлы меньше, и алгоритм работает очень хорошо. Недостатком является сложность реализации иерархического планировщика путей.[9]

Пример

А карта имеет размер 3000x2000 пиксели. Планирование пути на основе пикселей заняло бы очень много времени. Даже эффективный алгоритм потребуется вычислить множество возможных графиков. Причина в том, что такая карта будет содержать в целом 6 миллионов пикселей, а возможности исследования геометрического пространства чрезвычайно велики. Первым шагом для иерархического планировщика путей является разделение карты на более мелкие суб-карты. Каждый кластер имеет размер 300x200 пикселей. Общее количество кластеров 10x10 = 100. Во вновь созданном графе количество узлов невелико, можно перемещаться между 100 кластерами, но не внутри подробной карты. Если действительный путь был найден в графе высокого уровня, следующим шагом будет планирование пути в каждом кластере. Подкарта имеет размер 300x200 пикселей, которые могут обрабатываться обычным A * pathplanner с легкостью.

Алгоритмы, используемые при поиске пути

Многоагентный поиск пути

Поиск пути с несколькими агентами заключается в поиске путей для нескольких агентов от их текущих местоположений до их целевых местоположений без столкновения друг с другом, в то же время оптимизируя функцию затрат, такую ​​как сумма длин путей всех агентов. Это обобщение поиска пути. Многие многоагентные алгоритмы поиска пути являются обобщением A * или сводятся к другим хорошо изученным задачам, таким как целочисленное линейное программирование.[10] Однако такие алгоритмы обычно неполны; другими словами, не доказано, что решение может быть получено за полиномиальное время. Другая категория алгоритмов жертвует оптимальностью ради производительности, используя известные шаблоны навигации (например, поток трафика) или топологию проблемного пространства.[11]

Смотрите также

Рекомендации

  1. ^ «7.2.1 Проблема кратчайших путей из одного источника: алгоритм Дейкстры». Архивировано из оригинал на 2016-03-04. Получено 2012-05-18.
  2. ^ Деллинг, Д .; Сандерс, П.; Schultes, D .; Вагнер, Д. (2009). «Инженерные алгоритмы планирования маршрута». Алгоритмика больших и сложных сетей: проектирование, анализ и моделирование. Конспект лекций по информатике. 5515. Springer. С. 117–139. CiteSeerX  10.1.1.164.8916. Дои:10.1007/978-3-642-02094-0_7. ISBN  978-3-642-02093-3.
  3. ^ «5.7.1 Алгоритм Дейкстры».
  4. ^ «Введение в A * Pathfinding».
  5. ^ Кроуфорд, Крис (декабрь 1982 г.). «Приемы дизайна и идеи для компьютерных игр». БАЙТ. п. 96. Получено 19 октября 2013.
  6. ^ Сакердоти, граф Д. (1974). «Планирование в иерархии пространств абстракции» (PDF). Искусственный интеллект. 5 (2): 115–135. Дои:10.1016/0004-3702(74)90026-5.
  7. ^ Холте, Роберт С. и Перес, М.Б. и Циммер, Р.М. и Макдональд, А.Дж. (1995). Иерархический a *. Симпозиум по абстракции, переформулировке и аппроксимации.CS1 maint: несколько имен: список авторов (связь)
  8. ^ Пелехано, Нурия и Фуэнтес, Карлос (2016). «Иерархический поиск путей для навигационных сетей (HNA⁎)» (PDF). Компьютеры и графика. 59: 68–78. Дои:10.1016 / j.cag.2016.05.023. HDL:2117/98738.CS1 maint: несколько имен: список авторов (связь)
  9. ^ Ботеа, Ади и Мюллер, Мартин и Шеффер, Джонатан (2004). «Почти оптимальный иерархический поиск пути». Журнал разработки игр. 1: 7–28. CiteSeerX  10.1.1.479.4675.CS1 maint: несколько имен: список авторов (связь)
  10. ^ Ханг Ма, Свен Кениг, Нора Аянян, Лирон Коэн, Вольфганг Хёниг, Т. К. Сатиш Кумар, Тансель Урас, Хонг Сюй, Крейг Тови и Гуни Шарон. Обзор: обобщение многоагентного поиска пути к реальным сценариям. На 25-й Международной совместной конференции по искусственному интеллекту (IJCAI), семинар по поиску путей с несколькими агентами. 2016 г.
  11. ^ Хоршид, Мохтар (2011). «Полиномиальный алгоритм для неоптимального поиска пути с несколькими агентами». SOCS.

внешняя ссылка