Давайте предположим график с евклидовыми расстояниями. Источник s , а пункт назначения t .
Как известно, алгоритм Дейкстры посещает вершины x в порядке неубывающего расстояния ( s , x ).
Алгоритм A * посещает вершины x в порядке неубывающего расстояния ( s , x ) + h ( x ). Функция h должна быть допустимой эвристикой , что в этом значении означает, что h ( x ) ≤ расстояние ( x , т ). Рассмотрим различные варианты ч.
h ( x ) = 0. Это заставляет A * вести себя как Дейкстра.
ч ( х ) = расстояние ( х , т ). Это наилучшая возможная эвристика. A * будет посещать только те вершины, у которых расстояние ( s , x ) + расстояние ( x , t ) = расстояние ( s , t ), т. е. эти вершины находятся на кратчайшем пути от s до t . К сожалению, этот выбор h дорог для вычисления.
ч ( x ) = || x - t ||. Расстояние по прямой линии вычисляется за время O (1) и всегда является нижней границей расстояния.
Последняя эвристика работает хорошо, когда есть достаточно прямой выстрел от s до t , но, когда объезды накапливаются, A * посетит множество вершин, которые "с пути" ».
Седжвик – Виттер увеличивает его до 11, используя h ( x ) = a || x - t || для a > 1. Эта эвристика недопустима, поэтому мы не можем найти кратчайший путь, но, наказывая ранние объезды, мы надеемся, что она обрезает пространство поиска, не слишком сильно снижая качество решения.