Информатика / Алгоритмы и анализ данных

Алгоритм A*: кратчайший путь по оценке f=g+h

Алгоритм A* выбирает вершину по сумме уже пройденной стоимости g и допустимой оценки оставшегося пути h. При не завышающей эвристике он находит оптимальный маршрут и обычно просматривает меньше вершин, чем поиск Дейкстры.

Опубликовано: Обновлено:

Формула

$$f(v)=g(v)+h(v)$$
Схема Приоритет вершин A*
SABGg=2 h=2 f=4g=3 h=1 f=4g=5 h=0 f=5

Метки лучших найденных стоимостей в примере после обработки B. Веса ориентированных рёбер заданы в тексте; выделены дуги итогового маршрута S→A→B→G.

Обозначения

$g(v)$
стоимость лучшего известного пути от старта до v, единицы веса
$h(v)$
нижняя оценка стоимости от v до цели, единицы веса
$f(v)$
приоритет вершины в открытом множестве, единицы веса

Условия применения

Граф конечный, веса рёбер неотрицательны, старт и цель заданы. Эвристика h(v) должна быть допустимой: она не превышает истинную минимальную стоимость от v до цели. При консистентной эвристике закрытую вершину повторно открывать не нужно. Для допустимой, но несогласованной эвристики необходимо повторно открывать закрытую вершину, если её g улучшилось; также h цели равно нулю.

Ограничения

Если h=0, алгоритм превращается в Дейкстру. Завышенная эвристика может привести к неоптимальному пути. Манхэттенское расстояние допустимо при движении по четырём направлениям с единичной стоимостью; для иных весов нужна масштабированная нижняя оценка; диагонали или разные веса требуют другой оценки. В памяти хранятся открытые и закрытые вершины.

Подробное объяснение

Для каждой вершины A* хранит g — цену уже найденного пути от старта, и h — нижнюю оценку цены продолжения до цели. Их сумма f служит приоритетом: алгоритм расширяет наиболее многообещающую вершину, а не просто ближайшую к старту. При h=0 остаётся обычная стратегия Дейкстры.

Допустимость h означает h(v)≤h*(v), где h*(v) — настоящая минимальная стоимость до цели. Если g(v) соответствует оптимальному префиксу пути, f(v) не превышает стоимость полного оптимального пути через эту вершину. При ещё неоптимальном g такая гарантия для конкретной записи не следует из одной допустимости h. Когда цель извлечена из очереди с минимальным f, путь оптимален: любой ещё не раскрытый конкурентный путь имел бы приоритет не меньше найденной стоимости.

Консистентность задаётся условием h(u)≤w(u,v)+h(v). Тогда f не убывает вдоль пути, и закрытая вершина уже имеет окончательное g. Манхэттенская метрика на прямоугольной решётке с четырьмя направлениями обладает этим свойством.

Качество A* определяется также очередью с приоритетом, обработкой устаревших записей и восстановлением родителей. Разные равные f могут дать разные, но одинаково короткие маршруты. При динамических препятствиях найденный путь нужно проверять и планировать заново.

Нельзя останавливаться при первом обнаружении цели: цель должна быть извлечена как минимальная по f. Это важно при нулевой или слабой эвристике и неоднородных весах.

Как пользоваться формулой

  1. Задайте старт, цель, веса рёбер и эвристику h; проверьте, что h не завышает расстояние до цели.
  2. Положите старт в открытую очередь с g=0 и f=h; для остальных вершин установите бесконечное g.
  3. Извлекайте вершину с наименьшим f, рассматривайте её рёбра и улучшайте g соседей через текущую вершину.
  4. При улучшении g запишите родителя и новый приоритет; при несогласованной h повторно откройте ранее закрытую вершину.
  5. Остановитесь, когда цель извлечена минимальной по f, восстановите маршрут по родителям и проверьте его стоимость.

Историческая справка

Идея направленного поиска кратчайшего пути выросла из алгоритма Дейкстры 1959 года и эвристического поиска в задачах искусственного интеллекта. В 1968 году Питер Харт, Нильс Нильссон и Бертрам Рафаэль описали стратегию выбора по сумме стоимости пройденного пути и оценки оставшегося пути; название A* закрепилось за процедурой.

Ключевой результат авторов — условие, при котором эвристическая оценка сохраняет оптимальность. Позднее алгоритм стал стандартом для карт, игр и планирования движения. Современные реализации уточняют работу с консистентными эвристиками, памятью и повторным поиском при изменении карты. Условия допустимости и консистентности отделяют корректное доказательство от простой эвристической догадки: направление поиска не заменяет проверку стоимости.

Историческая линия формулы

Алгоритм A* обычно связывают с публикацией Харта, Нильссона и Рафаэля 1968 года. Это развитие более раннего поиска Дейкстры и эвристического поиска; формула f=g+h объединяет точную накопленную стоимость с нижней оценкой продолжения.

Пример

На графе есть старт S, цель G и рёбра S→A=2, S→B=5, A→B=1, A→G=7, B→G=2. Эвристики: h(S)=3, h(A)=2, h(B)=1, h(G)=0; каждая не превышает истинное расстояние до G. В начале f(S)=3. После S: A имеет g=2,f=4, B — g=5,f=6. Извлекаем A: через A получаем B с g=3,f=4 и G с g=9,f=9. Извлекаем B: через него G получает g=5,f=5. Теперь G имеет минимальный f и извлекается. Маршрут S→A→B→G, стоимость 2+1+2=5. Проверка: S→B→G стоит 7, а путь через A напрямую 9, поэтому найденный маршрут минимален. Проверка независимым перебором: среди путей без циклов стоимости 5, 7 и 9 минимальна стоимость 5; значит результат очереди согласуется с полным просмотром кандидатов.

Частая ошибка

Нельзя считать любую оценку допустимой: завышенная h ломает гарантию оптимальности. Ошибка в знаке превращает f в g−h и уводит поиск от цели. Нельзя завершать работу при первом добавлении цели; нужно извлечь её с минимальным f. При разных весах нельзя использовать число клеток вместо взвешенного расстояния. Также важно не потерять улучшение g уже открытой вершины.

Практика

Задачи с решением

Выбор очереди

Условие. Для X известны g=7,h=4, для Y g=5,h=8. Какую вершину A* выберет?

Решение. f(X)=11, f(Y)=13; минимум у X.

Ответ. Сначала X.

Проверка эвристики

Условие. Истинное расстояние от V до цели равно 12, h(V)=9. Допустима ли оценка?

Решение. 9≤12, значит оценка не завышает истинную стоимость.

Ответ. Да, допустима.

Дополнительные источники

  • https://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/astar.pdf
  • https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/astarNilsson.pdf

Связанные формулы

Математика

Хроматический многочлен графа: правило удаления и стягивания

$P_G(k)=P_{G-e}(k)-P_{G/e}(k)$

Хроматический многочлен P_G(k) считает правильные раскраски вершин графа в k цветов. Правило удаления и стягивания выражает его через два меньших графа и позволяет считать ответ рекурсивно.

Математика

Теорема Кирхгофа: число остовов через лапласиан

$\tau(G)=\det L^{(i)},\qquad L=D-A$

Число остовных деревьев неориентированного графа равно определителю любого главного минора его лапласиана. Теорема Кирхгофа заменяет перебор связных подграфов одним матричным вычислением.

Математика

Код Прюфера: число деревьев с заданными степенями

$N(d_1,\ldots,d_n)=\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!},\qquad d_i\ge1,\quad\sum_i d_i=2(n-1)$

В коде Прюфера метка вершины встречается на единицу меньше её степени. Поэтому число помеченных деревьев с фиксированной степенью каждой вершины равно мультиномиальному коэффициенту.

Математика

Формула Кэли: число деревьев с помеченными вершинами

$T_n=n^{n-2},\qquad n\ge2$

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