Поиск пути или прокладка пути — это поиск компьютерным приложением кратчайшего пути между двумя точками. Это более практичный вариант решения лабиринтов . Эта область исследований в значительной степени основана на алгоритме Дейкстры для поиска кратчайшего пути на взвешенном графе .
Поиск пути тесно связан с задачей поиска кратчайшего пути в теории графов , которая изучает, как определить путь, наилучшим образом отвечающий некоторым критериям (кратчайший, самый дешевый, самый быстрый и т. д.) между двумя точками в большой сети.
По своей сути, метод поиска пути ищет граф , начиная с одной вершины и исследуя смежные узлы , пока не будет достигнут узел назначения, как правило, с целью найти самый дешевый маршрут. Хотя методы поиска графа, такие как поиск в ширину, найдут маршрут, если дать им достаточно времени, другие методы, которые «исследуют» граф, будут стремиться достичь пункта назначения раньше. Аналогией может служить человек, идущий по комнате; вместо того, чтобы заранее изучить все возможные маршруты, человек обычно идет в направлении пункта назначения и отклоняется от пути только для того, чтобы избежать препятствия, и делает отклонения как можно менее значительными.
Две основные проблемы поиска пути: (1) найти путь между двумя узлами в графе ; и (2) задача кратчайшего пути — найти оптимальный кратчайший путь . Базовые алгоритмы, такие как поиск в ширину и в глубину, решают первую проблему, исчерпывая все возможности; начиная с заданного узла, они перебирают все потенциальные пути, пока не достигнут узла назначения. Эти алгоритмы работают за , или линейное время, где V — количество вершин, а E — количество ребер между вершинами.
Более сложная проблема — поиск оптимального пути. Исчерпывающий подход в этом случае известен как алгоритм Беллмана–Форда , который дает временную сложность , или квадратичное время. Однако не обязательно проверять все возможные пути, чтобы найти оптимальный. Такие алгоритмы, как A* и алгоритм Дейкстры, стратегически исключают пути, либо с помощью эвристики , либо с помощью динамического программирования . Исключая невозможные пути, эти алгоритмы могут достичь временной сложности всего лишь . [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* проверяет меньшее количество узлов, но больше не гарантирует оптимальный путь. Во многих приложениях (например, в видеоиграх) это приемлемо и даже желательно, чтобы поддерживать быструю работу алгоритма.
Поиск пути имеет историю включения в видеоигры с движущимися объектами или NPC. Крис Кроуфорд в 1982 году описал, как он «потратил много времени», пытаясь решить проблему с поиском пути в Tanktics , в которой компьютерные танки застряли на суше внутри U-образных озер. «После многих напрасных усилий я нашел лучшее решение: удалить U-образные озера с карты», - сказал он. [5]
Идея была впервые описана в индустрии видеоигр , которая нуждалась в планировании на больших картах с небольшим количеством процессорного времени . Концепция использования абстракции и эвристики старше и впервые была упомянута под названием ABSTRIPS (Abstraction-Based STRIPS ) [6] , которое использовалось для эффективного поиска в пространствах состояний логических игр. [7] Похожая техника — навигационные сетки (navmesh), которые используются для геометрического планирования в играх и планирования мультимодальных перевозок , которое применяется в задачах коммивояжера с более чем одним транспортным средством.
Карта разделена на кластеры . На верхнем уровне планируется путь между кластерами. После того, как план найден, второй путь планируется в кластере на нижнем уровне. [8] Это означает, что планирование выполняется в два этапа, что представляет собой направленный локальный поиск в исходном пространстве. Преимущество в том, что количество узлов меньше, а алгоритм работает очень хорошо. Недостаток в том, что иерархический планировщик пути трудно реализовать. [9]
Карта имеет размер 3000x2000 узлов. Планирование пути на основе узлов займет очень много времени. Даже эффективному алгоритму потребуется вычислить множество возможных графов. Причина в том, что такая карта будет содержать в целом 6 миллионов узлов, а возможности исследования геометрического пространства чрезвычайно велики. Первым шагом для иерархического планировщика пути является разделение карты на более мелкие подкарты. Каждый кластер имеет размер 300x200 узлов. Общее количество кластеров составляет 10x10=100. В недавно созданном графе количество узлов невелико, можно перемещаться между 100 кластерами, но не внутри подробной карты. Если в высокоуровневом графе был найден допустимый путь, следующим шагом является планирование пути внутри каждого кластера. Подкарта имеет 300x200 узлов, с которыми может легко справиться обычный планировщик пути A* .
Многоагентный поиск пути заключается в поиске путей для нескольких агентов из их текущих местоположений в их целевые местоположения без столкновений друг с другом, в то же время оптимизируя функцию стоимости, такую как сумма длин путей всех агентов. Это обобщение поиска пути. Многие многоагентные алгоритмы поиска пути обобщены из A* или основаны на сведении к другим хорошо изученным проблемам, таким как целочисленное линейное программирование. [10] Однако такие алгоритмы, как правило, неполны; другими словами, не доказано, что они дают решение за полиномиальное время. Некоторые параллельные подходы, такие как Collaborative Diffusion , основаны на ошеломляюще параллельных алгоритмах, распространяющих многоагентный поиск пути в вычислительные сетчатые структуры, например, ячейки, похожие на клеточные автоматы . Другая категория алгоритмов жертвует оптимальностью ради производительности, либо используя известные навигационные шаблоны (например, поток трафика), либо топологию проблемного пространства. [11]
{{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка ){{cite journal}}: CS1 maint: multiple names: authors list (link){{cite journal}}: CS1 maint: multiple names: authors list (link)