Личный кабинет
Подробное описание документа
Басараб М. А.
Алгоритмы решения задачи быстрого поиска пути на географических картах / Басараб М. А., Домрачева А. Б., Купляков В. М. - DOI 10.18698/2308-6033-2013-11-1054 // Инженерный журнал: наука и инновации. - 2013. - № 11. -
Скачать документ
Рассмотрены алгоритмы, позволяющие для подготовленного ландшафта предоставить один из возможных вариантов пути из одной точки в другую на географической карте с учетом особенностей проходимости местности. Описаны методы, которые условно можно разделить на следующие классы: алгоритмы поиска кратчайшего пути (Дейкстры); алгоритмы поиска субоптимального пути (A* и его модификации, в частности Theta*); алгоритмы постобработки маршрутов (удаление точек, лежащих на одной прямой; Line of Sight). Особое внимание уделено эвристическим алгоритмам, позволяющим найти близкий к оптимальному и в достаточной степени реалистично выглядящий маршрут. Описаны способы интерпретации ландшафта. Представлены выводы о применимости отдельных алгоритмов и их комбинаций. Сделан вывод о целесообразности использования различных алгоритмов на этапах построения предварительного варианта маршрута и его оптимизации. Произведен анализ различных методов поиска пути: их длины, сложности, числа точек поворота, суммарного угла отклонения.
Статья опубликована в следующих изданиях
№ 11. - 2013.
