A * использует функцию f(x) = g(x) + h(x), чтобы оценить, какой узел посетить следующим, где g(x) - это фактическая стоимость перехода от начала к x, а h(x) - приблизительная стоимость перехода от x. к цели (= эвристика).
Давайте посмотрим на это в непрерывном случае на евклидовой плоскости, где мы хотим перейти от (0, 0) до (10, 20). Тогда:
g(x) = Length(x)
Форма фронта исследования сильно зависит от эвристики. Начнем с идеальной эвристики
h(x) = Length(x - (10, 20))
Мы можем построить значение g(x) + h(x) на плоскости и увидеть порядок посещенных узлов (точки с меньшим f будут посещаться первыми). При этом мы должны знать, что узел не может быть посещен, если ни один из его соседей не был ранее, поэтому фактическое значение является только указанием порядка. Мы будем иметь это в виду. Используя идеальную эвристику, получаем следующую картину:
Все точки на связи между началом и целью имеют одинаковую стоимость f, которая равна расстоянию до начала и цели. И если мы проверяем f, мы видим, что
f = Length(x - (0, 0)) + Length(x - (10, 20)),
, которая является неявной формой эллипса с началом и целью в качестве фокусов.
Я сказал, что форма зависит от эвристики. Эвристика действительна, если она является нижней границей фактического расстояния. Давайте попробуем
h(x) = 0.5 * Length(x - (10, 20))
Теперь алгоритм начнет исследовать больше точек вокруг начала, прежде чем достигнет цели. В частности, все точки в контуре до целевой точки будут посещены.
Мы можем пойти еще дальше и установить
h(x) = 0
Это настройка для алгоритма Дейкстры, где мы не можем ничего сказать о расстоянии до цели:
Здесь алгоритм будет посещать узлы на дисках вокруг начальной точки.
Одним из распространенных приближений расстояния до цели является расстояние до Манхэттена, потому что это дешево для вычисления:
h(x, y) = |x - 10| + |y - 20|
Эта эвристика недопустима, поскольку она не является нижней границей действительного расстояния. Это дает нам:
Это как раз тот случай, когда точки, близкие к цели, имеют более низкий балл f, чем точки, близкие к началу. Хотя они имеют более низкое значение на этом рисунке, их, конечно, не посетят первыми, потому что их соседи еще не исследованы. Вот крупный план:
Мы можем сделать эвристику действительной, введя постоянный множитель:
h(x, y) = 1/sqrt(2) * (|x - 10| + |y - 20|)
Это даст нам правильную эвристику с правильной формой фронта:
