Найти путь - Pathfinding

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

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

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

Алгоритмы

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

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

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

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

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

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

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

Алгоритм A *

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

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

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

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

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X

Сначала создайте список координат, который мы будем использовать в качестве очереди. Очередь будет инициализирована одной координатой, конечной координатой. К каждой координате также будет прикреплена переменная счетчика (цель этого скоро станет очевидной). Таким образом, очередь начинается как ((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 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X

Теперь начните с 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-образные озера с карты», - сказал он.

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

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

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

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

Пример

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

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

  • Алгоритм Дейкстры
  • Алгоритм поиска A * , частный случай алгоритма Дейкстры
  • D * семейство алгоритмов инкрементального эвристического поиска для задач, в которых ограничения меняются со временем или не полностью известны, когда агент впервые планирует свой путь
  • Алгоритмы планирования пути под любым углом , семейство алгоритмов для планирования путей, которые не ограничиваются движением по краям в графе поиска, разработанные, чтобы иметь возможность принимать любой угол и, таким образом, находить более короткие и прямые пути

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

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

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

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

Внешние ссылки