Алгоритмы решения задачи быстрого поиска
пути на географических картах
11
Рис. 2.
Сравнение пути A* (красная линия) c путем Theta* (синяя линия)
Заключение.
Главная проблема задачи поиска пути заключается в
том, что не существует какого-либо универсального алгоритма ее
решения. Вместе с тем, на основании проведенных исследований
можно сделать вывод, что в случае поиска пути на географических
картах необходимо выбирать один из следующих способов решения
задачи. Если требуется получить наиболее реалистично выглядящий
субоптимальный путь, рекомендуется использовать алгоритм Theta*.
Когда затраты на обращение к ландшафту оказываются критичными,
рекомендуется использовать следующую комбинацию алгоритмов:
•
применяем алгоритм A* для получения маршрута;
•
удаляем точки, лежащие на одной прямой;
•
для каждой пары из небольшого множества полученных
ключевых точек применяем алгоритм проверки наличия пути по
прямой. Можно применять этот алгоритм только к соседним
отрезкам пути, разбивая их путем внедрения фиктивных точек.
В общем случае необходимо строить систему алгоритмов,
имеющих схожие входные и выходные данные, что позволит обмени-
ваться данными на отдельных шагах, комбинируя различные подхо-
ды к решению задачи. Помимо этого, немаловажным окажется вве-
дение иерархии: объединяя отдельные области ландшафта, можно
прокладывать пути сначала между крупными областями, потом,
применяя другие алгоритмы, — на отдельных участках, и дальше по
аналогии [3].
