РУсскоязычный Архив Электронных СТатей периодических изданий
Найти!
Инженерный журнал: наука и инновации/2013/№ 11/
В наличии за
50 руб.
Купить
Облако ключевых слов*
* - вычисляется автоматически
Недавно смотрели:

Алгоритмы решения задачи быстрого поиска пути на географических картах

Рассмотрены алгоритмы, позволяющие для подготовленного ландшафта предоставить один из возможных вариантов пути из одной точки в другую на географической карте с учетом особенностей проходимости местности. Описаны методы, которые условно можно разделить на следующие классы: алгоритмы поиска кратчайшего пути (Дейкстры), алгоритмы поиска субоптимального пути (A* и его модификации, в частности Theta*), алгоритмы постобработки маршрутов (удаление точек, лежащих на одной прямой, Line of Sight). Особое внимание уделено эвристическим алгоритмам, позволяющим найти близкий к оптимальному и в достаточной степени реалистично выглядящий маршрут. Описаны способы интерпретации ландшафта. Представлены выводы о применимости отдельных алгоритмов и их комбинаций. Сделан вывод о целесообразности использования различных алгоритмов на этапах построения предварительного варианта маршрута и его оптимизации. Произведен анализ различных методов поиска пути: их длины, сложности, числа точек поворота, суммарного угла отклонения.

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

Похожие документы:

  • Похожие документы из РУАЭСТ
  • |
  • Похожие документы из Руконт

Помощь:

Участники:

© НЦР Руконт 2014