Введение

Прокладка маршрута с помощью компьютерного приложения

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

Алгоритмы

В основе метода поиска пути лежит поиск по графу, начиная с одной вершины и исследуя смежные узлы до тех пор, пока не будет достигнут целевой узел, как правило, с целью нахождения наиболее дешевого маршрута. Хотя методы поиска по графам, такие как поиск в ширину, найдут маршрут при достаточном времени, другие методы, которые "прощупывают" граф, как правило, достигают цели быстрее. Можно провести аналогию с человеком, идущим через комнату: вместо того, чтобы заранее рассматривать все возможные маршруты, человек обычно идет в направлении цели и отклоняется от пути только для обхода препятствий, стараясь минимизировать эти отклонения. Две основные задачи поиска пути: (1) найти путь между двумя узлами в графе и (2) задача поиска кратчайшего пути – найти оптимальный кратчайший путь. Базовые алгоритмы, такие как поиск в ширину и поиск в глубину, решают первую задачу, перебирая все возможные варианты: начиная с заданного узла, они последовательно просматривают все потенциальные пути, пока не достигнут целевого узла. Эти алгоритмы выполняются за O(V+E), или линейное время, где V – количество вершин, а E – количество ребер между вершинами. Более сложная задача – найти оптимальный путь. Полный перебор в этом случае известен как алгоритм Беллмана-Форда, который имеет временную сложность O(VE), или квадратичное время. Однако для нахождения оптимального пути не обязательно рассматривать все возможные пути. Алгоритмы, такие как 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* исследует меньше узлов, но перестаёт гарантировать нахождение оптимального пути. Во многих приложениях (например, в видеоиграх) это допустимо и даже желательно, чтобы алгоритм работал быстрее.

В видеоиграх

Крис Кроуфорд в 1982 году описал, как он "потратил много времени", пытаясь решить проблему с прокладкой пути в Tanktics, где компьютерные танки застревали на суше внутри озер в форме буквы U. "После долгих безуспешных попыток я обнаружил более простое решение: убрать озера в форме буквы U с карты", – сказал он.

Иерархическое нахождение пути

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

Пример

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

Многоагентное определение пути

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