М.А. Басараб, А.Б. Домрачева, В.М. Купляков
8
алгоритмов моделирования, работающих в реальном времени, когда
требуется получить не конечный путь, а некоторый его участок.
Алгоритм A*.
Алгоритм A* является одним из наиболее
известных алгоритмов поиска субоптимального пути [2]. Он находит
маршрут от начальной вершины к конечной с наименьшей стои-
мостью. Порядок обхода определяется эвристической функцией
«расстояние + стоимость»:
f
(
x
) =
g
(
x
) +
h
(
x
). Функция
h
(
x
) должна
быть допустимой эвристической оценкой, т. е. не должна переоцени-
вать расстояние к целевой вершине. Она может представлять собой
расстояние до цели по прямой, так как это наименьшее расстояние
между двумя точками.
Алгоритм A* пошагово просматривает все пути от начальной
вершины до конечной, пока не найдет минимальный. Как и все
информированные алгоритмы поиска, он просматривает сначала те
маршруты, которые «кажутся» ведущими к цели. От жадного ал-
горитма (который также является алгоритмом поиска по первому
лучшему совпадению) его отличает то, что при выборе вершины он
учитывает, помимо прочего, весь пройденный до нее путь (сос-
тавляющая
g
(
x
) — это стоимость пути от начальной вершины, а не от
предыдущей, как в жадном алгоритме).
Алгоритм A* является полным, т. е. всегда находит решение,
если оно существует. Он также оптимально эффективен для заданной
эвристики
h
. Это значит, что любой другой алгоритм исследует не
меньше узлов, чем алгоритм A* (за исключением случаев, когда
существует несколько частных решений с одинаковой эвристикой,
точно соответствующей стоимости оптимального пути).
В то время как алгоритм A* оптимален для «случайно» заданных
графов, нет гарантии, что он сделает свою работу лучше, чем более
простые, но и более информированные относительно проблемной
области алгоритмы. Например, в некотором лабиринте может
потребоваться сначала идти по направлению от выхода, и только
потом повернуть назад. В этом случае обследование вначале тех
вершин, которые расположены ближе к выходу (по прямой), будет
потерей времени.
Рассмотрим модификации алгоритма A* и другие эвристические
алгоритмы субоптимального поиска.
Beam search (поиск по лучу).
В случае обычной реализации
алгоритма A* в списке задействованных вершин сохраняются все
вершины, которые могут потребоваться для поиска пути. Алгоритм
Beam search [5] накладывает ограничение на размер этой очереди:
если множество задействованных вершин становится слишком
большим, вершины с наименьшей вероятностью получения лучшего
пути удаляются из множества. Единственным ограничением является
