Что такое алгоритм A* и чем он лучше Дейкстры?

Дейкстра расширяет поиск во все стороны одинаково — «кругом» от старта. Если цель одна и известно, где она, это расточительно. A* добавляет эвристику h(v) — оценку расстояния от вершины до цели — и выбирает из очереди вершину с наименьшим f(v) = g(v) + h(v). Поиск вытягивается в сторону цели.

Свойства эвристики:

• допустимая — никогда не переоценивает реальное оставшееся расстояние. Тогда A* гарантированно находит кратчайший путь;
• согласованная (монотонная) — для любого ребра h(v) ≤ w(v, u) + h(u). Тогда каждую вершину достаточно обработать один раз;
• h = 0 — A* превращается в Дейкстру;
• переоценивающая эвристика ускоряет поиск, но путь может оказаться не кратчайшим — иногда это сознательный выбор в играх.

Эвристики на сетке:

• 4 направления движения — манхэттенское расстояние |dx| + |dy|;
• 8 направлений — октильное или чебышёвское;
• свободное движение — евклидово расстояние.

Применения: навигация в играх и роботах, маршруты на картах (с дополнительными ускорениями вроде иерархий дорог), решение головоломок.

import heapq

def a_star(grid, start, goal):
    h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])   # манхэттен
    g = {start: 0}
    parent = {start: None}
    heap = [(h(start), start)]
    while heap:
        _, v = heapq.heappop(heap)
        if v == goal:
            break
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            u = (v[0] + dr, v[1] + dc)
            if 0 <= u[0] < len(grid) and 0 <= u[1] < len(grid[0]) and grid[u[0]][u[1]] != "#":
                if g[v] + 1 < g.get(u, float("inf")):
                    g[u], parent[u] = g[v] + 1, v
                    heapq.heappush(heap, (g[u] + h(u), u))
    return g.get(goal)