Поиск пути
В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Поиск пути или определение пути — это поиск с помощью компьютерного приложения кратчайшего маршрута между двумя точками. Это более практичный вариант решения лабиринтов . Эта область исследований в значительной степени основана на алгоритме Дейкстры для поиска кратчайшего пути на взвешенном графе .
Поиск пути тесно связан с задачей о кратчайшем пути в теории графов , которая исследует, как определить путь, который лучше всего соответствует некоторым критериям (самый короткий, самый дешевый, самый быстрый и т. д.) между двумя точками в большой сети.
Алгоритмы
[ редактировать ]По своей сути метод поиска пути ищет граф , начиная с одной вершины и исследуя соседние узлы до тех пор, пока не будет достигнут узел назначения, обычно с целью найти самый дешевый маршрут. Хотя методы поиска по графу, такие как поиск в ширину, могли бы найти маршрут, если бы им было предоставлено достаточно времени, другие методы, которые «исследуют» граф, имеют тенденцию достигать пункта назначения раньше. Аналогией может быть человек, идущий по комнате; вместо того, чтобы заранее изучать все возможные маршруты, человек обычно идет в направлении пункта назначения и отклоняется от пути только для того, чтобы избежать препятствия, и делает отклонения как можно меньшими.
Две основные проблемы поиска пути: (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* проверяет меньше узлов, но больше не гарантирует оптимальный путь. Во многих приложениях (например, в видеоиграх) это приемлемо и даже желательно, чтобы алгоритм работал быстро.
В видеоиграх
[ редактировать ]Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( январь 2017 г. ) |
Крис Кроуфорд в 1982 году описал, как он «потратил много времени», пытаясь решить проблему с поиском пути в Tanktics , в которой компьютерные танки застревали на суше в U-образных озерах. «После многих напрасных усилий я нашел лучшее решение: удалить U-образные озера с карты», - сказал он. [5]
Иерархический поиск пути
[ редактировать ]Идея была впервые описана в индустрии видеоигр , которая нуждалась в планировании на больших картах с малым количеством процессорного времени . Концепция использования абстракции и эвристики более старая и впервые была упомянута под названием ABSTRIPS (Abstraction-Based STRIPS ). [6] который использовался для эффективного поиска пространств состояний логических игр. [7] Аналогичным методом являются навигационные сетки (navmesh), которые используются для геометрического планирования в играх и планирования мультимодальных перевозок , которое используется в задачах коммивояжера с более чем одним транспортным средством.
Карта разбита на кластеры . На высокоуровневом уровне планируется путь между кластерами. После того, как план найден, внутри кластера на нижнем уровне планируется второй путь. [8] Это означает, что планирование выполняется в два этапа: управляемый локальный поиск в исходном пространстве. Преимущество в том, что количество узлов меньше и алгоритм работает очень хорошо. Недостаток заключается в том, что иерархический планировщик пути сложно реализовать. [9]
Пример
[ редактировать ]Карта . имеет размер 3000х2000 узлов Планирование пути на базе узлов займет очень много времени. Даже эффективный алгоритм должен будет вычислить множество возможных графов. Причина в том, что такая карта будет содержать в общей сложности 6 миллионов узлов, а возможности исследования геометрического пространства чрезвычайно велики. Первым шагом иерархического планировщика пути является разделение карты на более мелкие подкарты. Каждый кластер имеет размер 300x200 узлов. Общее количество кластеров составляет 10x10=100. Во вновь созданном графе количество узлов невелико, можно перемещаться между 100 кластерами, но не внутри подробной карты. Если в графе высокого уровня найден действительный путь, следующим шагом будет планирование пути внутри каждого кластера. Подкарта имеет узлы 300x200, которые легко обрабатываются обычным планировщиком путей A* .
Алгоритмы, используемые при поиске пути
[ редактировать ]- Алгоритм Дейкстры
- Алгоритм поиска A* , частный случай алгоритма Дейкстры
- D* семейство дополнительных эвристических алгоритмов поиска для задач, в которых ограничения меняются со временем или не полностью известны, когда агент впервые планирует свой путь.
- Алгоритмы планирования пути под любым углом - семейство алгоритмов планирования путей, которые не ограничены перемещением по ребрам в графе поиска, предназначенные для того, чтобы иметь возможность принимать любой угол и, таким образом, находить более короткие и прямые пути.
Мультиагентный поиск пути
[ редактировать ]Многоагентный поиск пути предназначен для поиска путей для нескольких агентов от их текущих местоположений до целевых местоположений, не сталкиваясь друг с другом, и в то же время оптимизирует функцию стоимости, например сумму длин путей всех агентов. Это обобщение поиска пути. Многие алгоритмы многоагентного поиска пути обобщены на основе A* или основаны на сведении к другим хорошо изученным задачам, таким как целочисленное линейное программирование. [10] Однако такие алгоритмы обычно неполны; другими словами, не доказано, что он дает решение за полиномиальное время. Некоторые параллельные подходы, такие как Collaborative Diffusion , основаны на поразительно параллельных алгоритмах, распространяющих многоагентный поиск пути на вычислительные сетчатые структуры, например, ячейки, подобные клеточным автоматам . Другая категория алгоритмов жертвует оптимальностью ради производительности, используя либо известные шаблоны навигации (например, поток трафика), либо топологию проблемного пространства. [11]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «7.2.1 Задача о кратчайших путях с одним источником: алгоритм Дейкстры» . Архивировано из оригинала 4 марта 2016 г. Проверено 18 мая 2012 г.
- ^ Деллинг, Д.; Сандерс, П .; Шультес, Д.; Вагнер, Д. (2009). «Алгоритмы инженерного планирования маршрутов». Алгоритма больших и сложных сетей: проектирование, анализ и моделирование . Конспекты лекций по информатике. Том. 5515. Спрингер. стр. 117–139. CiteSeerX 10.1.1.164.8916 . дои : 10.1007/978-3-642-02094-0_7 . ISBN 978-3-642-02093-3 .
- ^ «5.7.1 Алгоритм Дейкстры» .
- ^ «Введение в поиск пути A*» .
- ^ Кроуфорд, Крис (декабрь 1982 г.). «Техники и идеи проектирования компьютерных игр» . БАЙТ . п. 96 . Проверено 19 октября 2013 г.
- ^ Сакердоти, граф Д. (1974). «Планирование в иерархии пространств абстракции» (PDF) . Искусственный интеллект . 5 (2): 115–135. дои : 10.1016/0004-3702(74)90026-5 .
- ^ Холте, Роберт С., Перес, М.Б., Циммер, Р.М. и Макдональд, Эй.Дж. (1995). Иерархический a* . Симпозиум по абстракции, переформулировке и аппроксимации.
{{cite conference}}
: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Пелечано, Нурия и Фуэнтес, Карлос (2016). «Иерархический поиск пути для навигационных сеток (HNA⁎)» (PDF) . Компьютеры и графика . 59 : 68–78. дои : 10.1016/j.cag.2016.05.023 . hdl : 2117/98738 .
{{cite journal}}
: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Ботеа, Ади и Мюллер, Мартин и Шеффер, Джонатан (2004). «Почти оптимальный иерархический поиск пути». Журнал разработки игр . 1 :7–28. CiteSeerX 10.1.1.479.4675 .
{{cite journal}}
: CS1 maint: несколько имен: список авторов ( ссылка ) - ^ Ханг Ма, Свен Кениг, Нора Аянян, Лирон Коэн, Вольфганг Хёниг, ТК Сатиш Кумар, Тансель Урас, Хун Сюй, Крейг Тови и Гуни Шарон. Обзор: обобщение многоагентного поиска пути на реальные сценарии. На 25-й Международной совместной конференции по искусственному интеллекту (IJCAI), семинаре по многоагентному поиску пути. 2016.
- ^ Хоршид, Мохтар (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* и воронки.