Информатика / Алгоритмы и анализ данных
Алгоритм A*: кратчайший путь по оценке f=g+h
Алгоритм A* выбирает вершину по сумме уже пройденной стоимости g и допустимой оценки оставшегося пути h. При не завышающей эвристике он находит оптимальный маршрут и обычно просматривает меньше вершин, чем поиск Дейкстры.
Формула
Метки лучших найденных стоимостей в примере после обработки 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. Это важно при нулевой или слабой эвристике и неоднородных весах.
Как пользоваться формулой
- Задайте старт, цель, веса рёбер и эвристику h; проверьте, что h не завышает расстояние до цели.
- Положите старт в открытую очередь с g=0 и f=h; для остальных вершин установите бесконечное g.
- Извлекайте вершину с наименьшим f, рассматривайте её рёбра и улучшайте g соседей через текущую вершину.
- При улучшении g запишите родителя и новый приоритет; при несогласованной h повторно откройте ранее закрытую вершину.
- Остановитесь, когда цель извлечена минимальной по 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) считает правильные раскраски вершин графа в k цветов. Правило удаления и стягивания выражает его через два меньших графа и позволяет считать ответ рекурсивно.
Математика
Теорема Кирхгофа: число остовов через лапласиан
Число остовных деревьев неориентированного графа равно определителю любого главного минора его лапласиана. Теорема Кирхгофа заменяет перебор связных подграфов одним матричным вычислением.
Математика
Код Прюфера: число деревьев с заданными степенями
В коде Прюфера метка вершины встречается на единицу меньше её степени. Поэтому число помеченных деревьев с фиксированной степенью каждой вершины равно мультиномиальному коэффициенту.
Математика
Формула Кэли: число деревьев с помеченными вершинами
Формула Кэли считает неориентированные деревья на заданных n различных вершинах: связные графы без циклов. Метки вершин сохраняются, а расположение рисунка на плоскости не создаёт новых деревьев.