A*: Дейкстра, которая знает, куда идти

Если ты знаешь формулу f = g + h, понимаешь, что при h ≡ 0 получается Дейкстра, и видишь связь эвристики с потенциалами, листай до «Теперь сам».

Как думаешь, зачем искать во все стороны

Дейкстра из Москвы во Владивосток честно расходится кругом: она раскроет Петербург, Минск и Мурманск раньше, чем доберётся до Урала, - потому что они ближе. Прежде чем читать дальше, подумай: какую подсказку надо дать алгоритму, чтобы он предпочитал вершины «в сторону цели»? И почему эта подсказка не должна врать в большую сторону?

На что это похоже

Поиск дома в незнакомом городе. Можно обходить кварталы по кругу, расширяя радиус, - найдёшь обязательно, но долго. А можно пользоваться тем, что видно направление: идти по улицам, приближающим к цели, даже если формально это не ближайший перекрёсток. Компас не заменяет карту - он подсказывает, какой из равных вариантов пробовать первым.

Механизм: f = g + h

import heapq                                # та же куча, что у Дейкстры
                                            # adj и V - данные графа, заводятся снаружи

def a_star(start, goal, h):
    g = {start: 0}
    q = [(h(start), start)]                 # приоритет - ОЦЕНКА ПОЛНОГО пути
    while q:
        f, v = heapq.heappop(q)
        if v == goal:
            return g[v]                     # цель извлечена - ответ готов
        for u, w in adj[v]:
            ng = g[v] + w
            if u not in g or ng < g[u]:
                g[u] = ng
                heapq.heappush(q, (ng + h(u), u))
    return None

Три величины, которые важно не путать:

g(v) - НАСТОЯЩАЯ длина найденного пути от старта до v (то же, что dist у Дейкстры)
h(v) - ОЦЕНКА оставшегося пути от v до цели (эвристика, считается формулой, не поиском)
f(v) = g(v) + h(v) - оценка полной длины пути через v; по ней и выбирают

Предельные случаи стоит запомнить оба (знак ≡ читается «тождественно равно»: не «в этой точке совпало», а «равно нулю для каждой вершины»):

h ≡ 0                      → f = g → это в точности Дейкстра
h = настоящее расстояние   → раскрывается только то, что лежит на оптимальных путях
h слишком большое          → быстро, но ответ может оказаться не кратчайшим

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

Правило

A* выбирает из очереди вершину с наименьшим f(v) = g(v) + h(v), где g - пройденное расстояние, h - оценка остатка до цели. При h ≡ 0 это Дейкстра; чем точнее h, тем меньше раскрытых вершин. Цена операций та же, что у Дейкстры, - выигрыш в ЧИСЛЕ раскрытий, а не в цене одной. Эвристика - это потенциал: A* эквивалентен Дейкстре на графе с весами w'(u, v) = w(u, v) + h(v) − h(u).

Разбор: A* - это Дейкстра с потенциалами

Вернёмся к Джонсону. Там мы перевешивали рёбра как w'(u, v) = w(u, v) + h[u] − h[v] и получали задачу, у которой те же кратчайшие пути. Подставим в качестве потенциала эвристику: w'(u, v) = w(u, v) + h(v) − h(u).

Знаки здесь не «наоборот», а те же: перевес всегда выглядит как w + p(u) − p(v), где p - потенциал. У Джонсона потенциал - это h[v], расстояние ОТ фиктивного старта, и подстановка p = h даёт w + h[u] − h[v]. У A* потенциал - это −h(v), оценка расстояния ДО цели со знаком минус (чем ближе к цели, тем «ниже» вершина), и та же формула w + p(u) − p(v) даёт w − h(u) + h(v). Одно правило, два разных потенциала - отсюда и разный порядок слагаемых.

Посчитаем, во что превращается приоритет. Длина пути от старта до v по новым весам равна g(v) + h(v) − h(старт) - это та же телескопическая сумма, что в прошлой главе. Слагаемое h(старт) одинаково для всех вершин, значит порядок по новой длине совпадает с порядком по g(v) + h(v), то есть по f. Вывод: A* - это буквально Дейкстра на перевешенном графе, и никакой новой теории он не требует.

Отсюда же сразу видно условие, при котором всё работает: Дейкстре нужны неотрицательные веса, значит нужно w(u, v) + h(v) − h(u) >= 0, то есть h(u) <= w(u, v) + h(v). Это и есть условие СОГЛАСОВАННОСТИ эвристики, и ему посвящён следующий урок.

Разбор: сколько вершин экономится

Возьмём открытую сетку без препятствий, 16 × 10, старт в углу (0,0), цель - в конце той же строки, (15,0). Дейкстра раскрывает вершины по возрастанию расстояния от старта, то есть «ромбом» во все стороны: до цели с расстоянием 15 она успевает раскрыть 105 клеток из 160.

A* с манхэттенской эвристикой идёт по строке 0 и раскрывает ровно 15 клеток - весь путь и ничего больше. Почему: для клетки (x, y) здесь f = g + h = (x + y) + (15 − x) + y = 15 + 2y, и любая клетка вне нулевой строки сразу получает f больше минимального. Оба замера сделаны на движке курса, ответ у обоих алгоритмов одинаковый - 15.

Но это не «всегда в семь раз». Поставь цель в противоположный угол той же открытой сетки - и выигрыш исчезнет: там манхэттенская эвристика ТОЧНА, а оптимальных путей между углами столько, что f одинаково у КАЖДОЙ клетки прямоугольника между стартом и целью. Алгоритм не знает, какой из равных вариантов лучше, и при ничьей по f может раскрыть их все - то есть почти всю сетку, как и Дейкстра. Лечится это правилом разрыва ничьих: при равном f вперёд пускают вершину с меньшим h, то есть ту, что ближе к цели, - тогда A* идёт по одному пути и раскрывает порядка его длины. Выигрыш зависит ещё и от рельефа: лабиринт со стенами заставит A* исследовать тупики, а на карте с редкими дорогами расстояние по прямой сильно недооценивает путь, и алгоритм снова начнёт расходиться кругом.

Асимптотика A* с СОГЛАСОВАННОЙ эвристикой (о ней следующий урок) та же, что у Дейкстры: O((V + E)·log V). Выигрыш - практический, и измеряется он числом раскрытых вершин, а не строчкой оценки.

Что ломается без этого

Первое: класть в очередь f, а сравнивать потом g (или наоборот) - приоритет и величина должны быть согласованы, иначе порядок извлечений станет бессмысленным. Второе: пересчитывать h поиском по графу - эвристика обязана быть ДЕШЁВОЙ (формула по координатам, таблица предподсчёта); если её вычисление стоит как сам поиск, смысла нет. Третье: останавливаться, когда цель впервые попала в очередь: ответ готов только когда цель ИЗВЛЕЧЕНА - до этого её оценка может улучшиться. Четвёртое: применять A* там, где цели нет (нужны расстояния до всех вершин) - эвристика туда просто не подставляется, это задача Дейкстры. Пятое: брать эвристику «на глаз», не проверив, не переоценивает ли она остаток, - об этом следующий урок.

Зачем это в работе

A* - стандарт в играх (поиск пути юнитов по сетке или навигационной сетке), в навигации и робототехнике, в решении головоломок (пятнашки, кубик - там эвристики вроде суммы манхэттенских расстояний), в планировании действий. На больших дорожных графах его усиливают предподсчитанными эвристиками: выбирают «ориентиры» (landmarks), считают от них расстояния заранее и получают куда более точную оценку, чем расстояние по прямой, - это семейство называют ALT. И ещё одно практическое: A* естественно сочетается с двунаправленным поиском и с поиском по сетке с крупными блоками. Но главное, что стоит унести: никакой магии здесь нет - это Дейкстра, которой подсказали направление потенциалом.

Теперь сам

Сетка 3 × 3, ходить можно вверх/вниз/влево/вправо, каждый шаг стоит 1. Старт - клетка (0,0), цель - (2,2). Эвристика - манхэттенское расстояние. Посчитай f для клеток (0,1), (1,1) и (1,0) после первого шага и скажи, какую из них A* раскроет первой.