Алгоритм A*

A* — это расширение Дейкстры, которое добавляет эвристику h(n) — оценку оставшегося расстояния до цели. Вершины обрабатываются в порядке возрастания f(n) = g(n) + h(n), где g — пройденный путь. Это направляет поиск к цели и резко сокращает число рассмотренных вершин.

Сложность: зависит от качества эвристики; при допустимой (не переоценивающей) эвристике путь оптимален. Память: O(V). Широко применяется в играх и навигации.

import heapq

def a_star(graph, start, goal, h):
    g = {start: 0}
    pq = [(h(start), start)]
    while pq:
        _, v = heapq.heappop(pq)
        if v == goal:
            return g[v]
        for nb, w in graph[v]:
            ng = g[v] + w
            if ng < g.get(nb, float("inf")):
                g[nb] = ng
                heapq.heappush(pq, (ng + h(nb), nb))
    return None