Алгоритм A*: поиск пути с эвристикой простыми словами

Коротко

A* находит кратчайший путь между двумя точками и делает это заметно быстрее Дейкстры за счёт подсказки о направлении цели.

Проблема Дейкстры

Дейкстра ищет кратчайшие пути во все стороны сразу. Она не знает, где находится цель, поэтому расширяется равномерным кругом.

     Дейкстра                     A*
   . . . . . . .              . . . . . . .
   . o o o o o .              . . . o o o .
   . o o S o o .              . . o S o o C
   . o o o o o .              . . . o o o .
   . . . . . . .              . . . . . . .

   S — старт, C — цель, o — просмотренные клетки

Если цель справа, то все просмотренные клетки слева — потраченное впустую время. На большой карте это тысячи лишних узлов.

A* добавляет к оценке узла предположение о том, сколько ещё осталось до цели, и потому расширяется преимущественно в нужную сторону.

Формула

Для каждого узла считается:

f(n) = g(n) + h(n)

• g(n) — реальная стоимость пути от старта до n (это то же, что у Дейкстры);
• h(n) — эвристика, оценка оставшегося пути от n до цели;
• f(n) — общая ожидаемая стоимость маршрута через n.

Из очереди всегда извлекается узел с наименьшим f. Если h всегда равна нулю, A* превращается в Дейкстру — то есть Дейкстра это частный случай.

Допустимость: главное условие

Эвристика должна быть допустимой — то есть никогда не переоценивать реальное расстояние.

h(n) ≤ настоящее расстояние от n до цели

Если это условие выполняется, A* гарантированно находит кратчайший путь. Если нарушается — алгоритм всё равно найдёт какой-то путь, и быстрее, но он может оказаться неоптимальным.

Интуиция: завышенная оценка заставляет алгоритм считать хорошие маршруты плохими и отбрасывать их досрочно.

Есть и более сильное свойство — монотонность (согласованность): для любого ребра h(a) ≤ вес(a,b) + h(b). Монотонная эвристика допустима автоматически и гарантирует, что каждый узел обрабатывается лишь однажды.

Выбор эвристики для сетки

Правило: эвристика должна соответствовать способу передвижения. Манхэттенское расстояние на карте с диагоналями переоценит путь (по диагонали короче) и сломает оптимальность.

Чем ближе h к реальному расстоянию, тем меньше узлов просмотрит алгоритм. Идеальная эвристика (точное расстояние) свела бы поиск к прямому движению по маршруту, но её вычисление равносильно решению исходной задачи.

Реализация на Python

import heapq


def a_star(grid: list[list[int]], start: tuple, goal: tuple):
    """grid: 0 — проходимо, 1 — стена. Возвращает путь или None."""
    rows, cols = len(grid), len(grid[0])

    def heuristic(a: tuple, b: tuple) -> int:
        # манхэттенское расстояние — для 4 направлений
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    open_set = [(heuristic(start, goal), 0, start)]   # (f, g, узел)
    came_from = {}
    g_score = {start: 0}
    visited = set()

    while open_set:
        f, g, current = heapq.heappop(open_set)

        if current == goal:
            # восстанавливаем путь по ссылкам назад
            path = [current]
            while current in came_from:
                current = came_from[current]
                path.append(current)
            return path[::-1]

        if current in visited:
            continue          # устаревшая запись в куче
        visited.add(current)

        row, col = current
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            nr, nc = row + dr, col + dc
            neighbor = (nr, nc)

            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] == 1:
                continue

            tentative_g = g + 1        # вес ребра = 1

            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                heapq.heappush(
                    open_set,
                    (tentative_g + heuristic(neighbor, goal), tentative_g, neighbor)
                )

    return None      # пути нет


grid = [
    [0, 0, 0, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
]

path = a_star(grid, (0, 0), (4, 4))
print(path)
# [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), ... ]
print(len(path) - 1, 'шагов')

Ключевая деталь — в кучу кладём кортеж (f, g, узел). Второй элемент нужен не только для передачи g, но и как разделитель при равных f: без него Python попытается сравнить кортежи-координаты, что сработает, но даст непредсказуемый порядок.

Сравнение стратегий

Возьмём одну карту и посмотрим, сколько узлов просматривает каждый алгоритм.

Жадный поиск (best-first search) смотрит только на близость к цели и потому бежит напролом — быстро, но легко застревает за стенами и выдаёт кривые маршруты. A* сочетает оба сигнала и потому оптимален.

Взвешенный A*

Иногда оптимальность не нужна, а скорость критична. Тогда эвристику умножают на коэффициент больше единицы:

f = g + weight * h       # weight = 1.5, например

Алгоритм становится «жаднее» и просматривает меньше узлов. Гарантия оптимальности теряется, но есть полезное свойство: найденный путь не хуже оптимального более чем в weight раз. Это управляемый компромисс, который часто применяют в играх.

Где применяется

Игры — поиск пути для юнитов. Самое известное применение; A* фактически стандарт индустрии.

Навигация и маршрутизация — с эвристикой в виде расстояния по прямой. Реальные картографические сервисы используют более сложные варианты (contraction hierarchies), но идея та же.

Робототехника — планирование движения по карте препятствий.

Головоломки — пятнашки, кубик Рубика. Эвристика: число фишек не на своих местах или сумма манхэттенских расстояний.

Частые ошибки

Недопустимая эвристика. Самая коварная: путь находится, тесты на простых картах проходят, а на сложных маршрут оказывается неоптимальным. Всегда проверяйте, что h не может переоценить.

Несоответствие эвристики движениям. Манхэттенское расстояние при разрешённых диагоналях — типичный случай.

Отсутствие проверки на повторную обработку. Без visited узел может обрабатываться многократно, и алгоритм замедлится, хотя ответ останется верным.

Забытая проверка границ. На сетке легко выйти за массив; в Python отрицательный индекс не упадёт, а молча возьмёт элемент с конца — и путь «телепортируется» через карту.

Что запомнить

• A* = Дейкстра + подсказка о направлении цели: f = g + h.
• Эвристика обязана быть допустимой — не переоценивать оставшийся путь.
• Для сетки с 4 направлениями берите манхэттенское расстояние, с 8 — Чебышёва.
• При h = 0 алгоритм вырождается в Дейкстру.
• Умножение эвристики на коэффициент ускоряет поиск ценой контролируемой потери оптимальности.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→