ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Автор: Казачкин Даниил Михайлович · Обновлено
Алгоритм A* на собственном графе: цена пути, нижняя оценка остатка, неверная эвристика и условия корректного завершения поиска.
Игровой персонаж ищет путь к выходу. Полный перебор возможных маршрутов тратит время на направления, которые очевидно удаляются от цели. Но выбор только ближайшей к цели клетки тоже ненадёжен: между ней и выходом может стоять длинная стена. Нужен способ учитывать уже пройденную цену и разумное предположение о цене оставшегося пути.
A* присваивает состоянию приоритет f = g + h. Значение g — известная цена пути от старта, h — оценка оставшейся цены. Эвристика помогает выбирать, какую вершину раскрывать следующей. Однако для гарантии оптимального ответа недостаточно назвать её «умной»: она должна соблюдать математические ограничения, а реализация — корректно обновлять найденные пути.
Классическая работа Hart, Nilsson и Raphael 1968 года формализует эвристический поиск минимальных путей. В прикладном разборе здесь рассматривается конечный граф с неотрицательными стоимостями. Допустимая эвристика не завышает истинную минимальную оставшуюся стоимость; для цели h равна нулю. Первичная статья.
Согласованность — более сильное локальное условие: для ребра u → v оценка h(u) не превышает цену ребра плюс h(v). Она упрощает работу с уже обработанными вершинами. Если эвристика только допустима, реализации в общем случае может потребоваться повторное раскрытие вершины после улучшения пути. Поэтому переносить гарантию алгоритма на произвольный код с вечным closed-set нельзя.
Построим четыре вершины. Через A путь стоит 2 + 2 = 4, через B — 1 + 10 = 11. Код хранит лучшую найденную цену и разрешает обновить вершину, если появилась более дешёвая дорога. Устаревшие записи в очереди пропускаются. Все веса и оценки задаются локально, без сторонних библиотек.
from heapq import heappop, heappush
graph = {
"S": [("A", 2), ("B", 1)],
"A": [("G", 2)],
"B": [("G", 10)],
"G": [],
}
def astar(heuristic):
best = {"S": 0}
queue = [(heuristic["S"], 0, "S")]
while queue:
_, cost, node = heappop(queue)
if cost != best[node]:
continue
if node == "G":
return cost
for target, weight in graph[node]:
candidate = cost + weight
if candidate < best.get(target, float("inf")):
best[target] = candidate
heappush(queue, (candidate + heuristic[target], candidate, target))
return None
assert astar({"S": 4, "A": 2, "B": 10, "G": 0}) == 4
assert astar({"S": 0, "A": 100, "B": 0, "G": 0}) == 11
assert astar({node: 0 for node in graph}) == 4
print("optimal: 4; overestimated heuristic: 11")Первая эвристика точно равна остаточным расстояниям на этом игрушечном графе. На практике знать их заранее обычно невыгодно: их вычисление уже решает исходную задачу. Здесь точные числа нужны для проверки механизма. Вторая эвристика объявляет продолжение через A чрезмерно дорогим, и алгоритм извлекает цель с ценой 11, не исследовав лучший путь.
В третьем запуске все оценки нулевые. Приоритет определяется только уже известной ценой, что соответствует идее алгоритма Дейкстры. Так можно получить независимую контрольную конфигурацию для неотрицательного графа. Но совпадение на четырёх вершинах не доказывает корректность любой сложной реализации: нужны разнообразные графы и проверка предпосылок.
На прямоугольной сетке с четырьмя направлениями движения и ценой шага не меньше единицы манхэттенское расстояние даёт естественную нижнюю оценку. Препятствия заставляют обходить, но не сокращают необходимое число горизонтальных и вертикальных перемещений. Если добавить дешёвые диагонали или телепорты, прежнее объяснение перестаёт работать: оценку нужно пересмотреть под новые правила.
Это общий приём — решить упрощённую задачу, убрав часть ограничений так, чтобы путь мог стать только дешевле. Полученная стоимость служит кандидатом на нижнюю оценку исходной задачи. После этого отдельно доказывают соответствие единиц: нельзя складывать длину в клетках со временем в секундах без коэффициента, который связывает их и сохраняет нужную границу.
Для проверки используйте маленькие случайные графы, где точное решение можно получить контрольным алгоритмом. Сравнивайте не только найденную цену, но и число раскрытых вершин, объём очереди и время. Более дорогая эвристика иногда сокращает раскрытия, но увеличивает общее время вычисления. Кроме того, разрешение равных приоритетов влияет на объём работы и должно быть воспроизводимым.
Ещё одна тонкость — момент остановки. Найти ребро, ведущее к цели, недостаточно: другой ещё не раскрытый путь может оказаться дешевле. В коде завершение происходит при извлечении актуальной записи цели из очереди приоритетов. Сдвиг проверки внутрь цикла по соседям меняет аргумент корректности. Добавьте контрольный граф, где дорогое ребро к цели обнаруживается раньше дешёвого обхода, и убедитесь, что оптимизация раннего выхода не сломала результат. Это небольшое изменение управления потоком часто важнее сложности самой эвристики.
Документация NetworkX прямо предупреждает, что недопустимая эвристика может дать не кратчайший путь. Также важно читать ограничения конкретной реализации: изменение оценки по ходу поиска или веса, зависящие от истории маршрута, требуют другого состояния и протокола вычисления.
Наш код возвращает только стоимость, а для игрового маршрута потребуется хранить предшественников и восстанавливать последовательность шагов. В изменяющемся мире нужно решать, когда пересчитывать путь и какой снимок препятствий использован. A* полезен именно тогда, когда модель задачи, нижняя оценка и правила завершения согласованы. Ускорение становится обоснованным следствием информации о задаче, а не надеждой на правдоподобную подсказку.
Самостоятельный русскоязычный разбор ЯдроКода. Описания первоисточников отделены от авторских учебных примеров и инженерных выводов. Материал не является переводом или перепечаткой.
Учебные данные, расчёты, таблицы и программные примеры созданы для этой публикации. Иллюстрации и программный код из первоисточников не воспроизводятся.