Алгоритмы решения задачи быстрого поиска
пути на географических картах
9
требование поддерживать упорядоченность вершин в множестве, что,
в свою очередь, накладывает ограничения на используемые виды
контейнеров для хранения вершин.
Iterative deepening (итеративное погружение).
Алгоритм Iterative
deepening [5] позволяет производить более точные вычисления. Идея
его заключается в том, чтобы проверить следующие несколько шагов
алгоритма. Если при этом не достигается улучшение результата, то
делается предположение, что текущее решение уже является доста-
точно оптимальным, и вряд ли удастся его улучшить при проведении
аналогичных операций в том направлении. В алгоритме IDA*
производится регулировка глубины по уровню
f
: если значение
f
слишком велико, узел не будет рассматриваться. Таким образом, при
первом проходе будет проверено малое количество узлов. При
последующих проходах количество посещаемых узлов будет уве-
личиваться. В случае обнаружения улучшения пути следует про-
должить исследование, в противном случае вычисления можно
прерывать.
Dynamic weighting (использование переменных весов).
В случае
использования изменяющихся весов [4] мы предполагаем, что на
первых шагах алгоритма требуется как можно быстрее достичь области,
содержащей конечную точку пути. В финальной стадии поиска более
важным является достижение конкретной точки. Предлагается сле-
дующая модификация функции веса:
f
(
p
) =
g
(
p
) +
w
(
p
)
h
(
p
).
При приближении к конечной точке вес уменьшается. Это сни-
жает значимость эвристики и увеличивает относительную важность
фактической стоимости пути.
Bidirectional search (двунаправленный поиск).
В данной моди-
фикации [5] алгоритма A* поиск пути ведется одновременно из двух
вершин навстречу друг другу. Когда эти два пути встречаются, алго-
ритм завершает свою работу. Основной недостаток — отсутствие
универсальности: алгоритм не будет работать на всех типах карт. В
то же время он работает не с одним большим деревом поиска, а с
двумя маленькими, что позволяет уменьшить количество используе-
мой памяти.
Theta*.
Одна из основных проблем алгоритма A* (как и многих
других) заключается в том, что получаемые с его помощью пути не
выглядят реалистичными. Эта проблема решается в алгоритме Theta*
