Дейкстра раскрывает все вершины на одном расстоянии от источника и не знает, где цель. A\* (A-star) учитывает ещё и оценку оставшегося расстояния до цели (эвристику) и раскрывает сначала вершины, которые выглядят ближе к цели. Если эвристика корректна, результат так же оптимален, как у Дейкстры, но просматривается меньше вершин.

Одна сетка: Дейкстра просматривает 59 клеток, A* — 44
Одна сетка: Дейкстра просматривает 59 клеток, A* — 44

Приоритет f = g + h

g(n) — точное расстояние, уже пройденное от старта до n; h(n) — оценка оставшегося расстояния от n до цели. Из очереди (heapq) берётся вершина с наименьшим f(n) = g(n) + h(n). При h(n) = 0 алгоритм совпадает с Дейкстрой, а на невзвешенном графе — с BFS.

Допустимая и согласованная эвристика

  • Допустимая (admissible): h(n) никогда не больше реального остатка пути. Тогда A* находит оптимальный путь.
  • Согласованная (consistent): h(a) <= cost(a, b) + h(b) для каждого ребра. Согласованная эвристика всегда допустима, и каждая вершина раскрывается один раз.

На сетке с 4 направлениями и единичными шагами стандартный выбор — манхэттенское расстояние: оно не учитывает стены, поэтому не может превысить реальное. Евклидово расстояние тоже допустимо, но слабее.

python
import math

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def euclid(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])