Jump to content

Поиск пути

Эквивалентные пути между A и B в 2D-среде

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

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

Алгоритмы

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

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

Алгоритм А*

[ редактировать ]

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

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

В видеоиграх

[ редактировать ]

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

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

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

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

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

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

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

[ редактировать ]

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

[ редактировать ]

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

См. также

[ редактировать ]
  1. ^ «7.2.1 Задача о кратчайших путях с одним источником: алгоритм Дейкстры» . Архивировано из оригинала 4 марта 2016 г. Проверено 18 мая 2012 г.
  2. ^ Деллинг, Д.; Сандерс, П .; Шультес, Д.; Вагнер, Д. (2009). «Алгоритмы инженерного планирования маршрутов». Алгоритма больших и сложных сетей: проектирование, анализ и моделирование . Конспекты лекций по информатике. Том. 5515. Спрингер. стр. 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*» .
  5. ^ Кроуфорд, Крис (декабрь 1982 г.). «Техники и идеи проектирования компьютерных игр» . БАЙТ . п. 96 . Проверено 19 октября 2013 г.
  6. ^ Сакердоти, граф Д. (1974). «Планирование в иерархии пространств абстракции» (PDF) . Искусственный интеллект . 5 (2): 115–135. дои : 10.1016/0004-3702(74)90026-5 .
  7. ^ Холте, Роберт С., Перес, М.Б., Циммер, Р.М. и Макдональд, Эй.Дж. (1995). Иерархический a* . Симпозиум по абстракции, переформулировке и аппроксимации. {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )
  8. ^ Пелечано, Нурия и Фуэнтес, Карлос (2016). «Иерархический поиск пути для навигационных сеток (HNA⁎)» (PDF) . Компьютеры и графика . 59 : 68–78. дои : 10.1016/j.cag.2016.05.023 . hdl : 2117/98738 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  9. ^ Ботеа, Ади и Мюллер, Мартин и Шеффер, Джонатан (2004). «Почти оптимальный иерархический поиск пути». Журнал разработки игр . 1 :7–28. CiteSeerX   10.1.1.479.4675 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  10. ^ Ханг Ма, Свен Кениг, Нора Аянян, Лирон Коэн, Вольфганг Хёниг, ТК Сатиш Кумар, Тансель Урас, Хун Сюй, Крейг Тови и Гуни Шарон. Обзор: обобщение многоагентного поиска пути на реальные сценарии. На 25-й Международной совместной конференции по искусственному интеллекту (IJCAI), семинаре по многоагентному поиску пути. 2016.
  11. ^ Хоршид, Мохтар (2011). «Алгоритм полиномиального времени для неоптимального многоагентного поиска пути» . СОКС .
[ редактировать ]
  • https://melikpehlivanov.github.io/AlgorithmVisualizer
  • http://sourceforge.net/projects/argorha
  • StraightEdge с открытым исходным кодом Java 2D для поиска пути (с использованием A *) и проекта освещения. Включает демонстрационные версии апплетов.
  • python-pathfinding 2D-путепоиск пути на Python с открытым исходным кодом (с использованием алгоритма Дейкстры) и проект освещения.
  • Daedalus Lib с открытым исходным кодом. Daedalus Lib управляет полностью динамическим триангулированным 2D-моделированием среды и поиском пути с помощью алгоритмов A* и воронки.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 9f478a39fa05cffc8f1f1b08752220a6__1717442340
URL1:https://arc.ask3.ru/arc/aa/9f/a6/9f478a39fa05cffc8f1f1b08752220a6.html
Заголовок, (Title) документа по адресу, URL1:
Pathfinding - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)