1
УДК 519.16
Алгоритмы решения задачи быстрого поиска пути
на географических картах
© М.А. Басараб, А.Б. Домрачева, В.М. Купляков
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Рассмотрены алгоритмы, позволяющие для подготовленного ландшафта предо-
ставить один из возможных вариантов пути из одной точки в другую на геогра-
фической карте с учетом особенностей проходимости местности. Описаны ме-
тоды, которые условно можно разделить на следующие классы: алгоритмы
поиска кратчайшего пути (Дейкстры); алгоритмы поиска субоптимального пути
(A* и его модификации, в частности Theta*); алгоритмы постобработки марш-
рутов (удаление точек, лежащих на одной прямой; Line of Sight). Особое внимание
уделено эвристическим алгоритмам, позволяющим найти близкий к оптимальному
и в достаточной степени реалистично выглядящий маршрут. Описаны способы
интерпретации ландшафта. Представлены выводы о применимости отдельных
алгоритмов и их комбинаций. Сделан вывод о целесообразности использования
различных алгоритмов на этапах построения предварительного варианта марш-
рута и его оптимизации. Произведен анализ различных методов поиска пути:
их длины, сложности, числа точек поворота, суммарного угла отклонения.
Ключевые слова:
поиск пути, алгоритм Дейкстры, алгоритм A*, алгоритм Theta*.
Введение.
При создании симуляторов, подразумевающих пере-
мещение различных типов объектов по большим территориям с учетом
текущей тактической обстановки, возникают проблемы с выбором
алгоритма поиска оптимального пути, так как на его использование
накладываются ограничения, вызванные следующими факторами:
•
большой объем данных реальных карт местности, превы-
шающий объем оперативной памяти, поэтому в большинстве случаев
нет возможности хранить полную информацию о промежуточном
состоянии маршрута в памяти;
•
сложность представления ландшафта (территории), по кото-
рому перемещаются объекты, это требует минимизации числа запро-
сов на определение проходимости определенного участка пути;
•
большой разброс в сложности получаемого пути:
оптимальным решением может оказаться как прямая, так и сильно
изломанная линия.
Кроме указанных, при реализации конкретных алгоритмов может
возникать ряд других проблем.
Существует большое количество алгоритмов, позволяющих
определить маршрут, по которому можно попасть из одной точки в
другую. Эти алгоритмы можно разбить на две группы:
•
алгоритмы, позволяющие определить оптимальный путь [1];
•
алгоритмы, позволяющие найти субоптимальный путь [2–5].
