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