Алгоритмы
A*: Эвристический поиск пути
Цели урока
- Понять ограничения Dijkstra и идею эвристического поиска
- Освоить формулу f = g + h и её смысл
- Выбирать правильную эвристику для задачи
- Понимать требование допустимости для оптимальности
- Реализовать A* для поиска пути на сетке
Предварительные знания
- Алгоритм Dijkstra
- BFS для графов
- Приоритетная очередь
A* - золотой стандарт поиска пути в играх и навигации.
- GPS-навигаторы используют A* для построения маршрутов
- Игры: pathfinding NPC, стратегии
- Робототехника: планирование траектории
A* и робот Шеки из SRI
Алгоритм A* придумали Питер Харт, Нильс Нильссон и Бертрам Рафаэль в Стэнфордском исследовательском институте (SRI) в 1968 году. Им нужно было научить робота Шеки (Shakey), первого мобильного робота, способного рассуждать о своих действиях, прокладывать путь между комнатами. В статье 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths' они объединили равномерный поиск Дейкстры с эвристической оценкой расстояния до цели и доказали, что при допустимой эвристике A* находит оптимальный путь. С тех пор это базовый алгоритм поиска пути в играх, робототехнике и навигации.
Проблема Dijkstra: поиск вслепую
Dijkstra находит кратчайший путь, но делает это **вслепую** - он не знает, где находится цель. Алгоритм исследует все направления равномерно, как круги на воде.
**Метафора: поиск выхода из лабиринта**
В лабиринте ищется выход. Dijkstra - это как идти во все стороны одновременно, отправляя клонов в каждый коридор. В итоге выход найдётся, но исследуется куча тупиков.
А теперь: слышен шум улицы (выход рядом!). Разумно идти в направлении шума, а не во все стороны. Это и есть идея A* - использовать **подсказку** (эвристику) о направлении к цели.
Dijkstra гарантирует оптимальный путь, но может быть медленным. A* тоже гарантирует оптимальный путь (при правильной эвристике), но работает быстрее.
Почему Dijkstra может быть неэффективен для поиска пути к конкретной точке?
Dijkstra не использует информацию о положении цели, поэтому исследует много 'лишних' направлений.
Идея A*: умный приоритет
A* - это Dijkstra с **подсказкой**. Вместо того чтобы выбирать вершину с минимальным расстоянием от старта, A* выбирает вершину с минимальной **оценкой общего пути**.
**Формула A*:**
**Почему это работает?**
g(n) - то, что уже потрачено. h(n) - оценка того, что ещё потратится. Вместе они дают оценку **полного пути** через n. Выбирается путь с лучшей общей оценкой.
**Метафора: выбор маршрута на карте**
Маршрут из Москвы в Питер. Есть два варианта:
1) Через Тверь: уже проехал 100 км (g), до Питера ещё ~550 км (h), итого ~650 км (f)
2) Через Новгород: уже проехал 300 км (g), до Питера ещё ~200 км (h), итого ~500 км (f)
Хотя через Тверь пройдено меньше (меньше g), общий путь через Новгород короче (меньше f). A* выберет Новгород!
A* 'смотрит вперёд'. Dijkstra оценивает только пройденный путь, A* оценивает весь путь включая оставшийся.
Что означает f(n) = g(n) + h(n) в A*?
g(n) - реальное расстояние от старта, h(n) - эвристическая оценка до цели, f(n) - их сумма, общая оценка пути.
Эвристики: как оценить расстояние?
**Эвристика h(n)** - это функция, которая оценивает расстояние от точки n до цели. Выбор эвристики критически важен!
**Для сетки (grid) есть несколько стандартных эвристик:**
**1. Манхэттенское расстояние** - для движения только по горизонтали/вертикали (4 направления):
**2. Евклидово расстояние** - для движения в любом направлении:
**3. Чебышевское расстояние** - для 8 направлений (вкл. диагонали, все стоят одинаково):
**4. Октильное расстояние** - для 8 направлений (диагональ стоит √2):
Выбор эвристики зависит от правил движения в конкретной задаче. Эвристика должна соответствовать реальным возможностям.
Какая эвристика подходит для сетки с движением только вверх/вниз/влево/вправо?
Манхэттенское расстояние |Δx| + |Δy| точно соответствует минимальному пути в 4-связной сетке без препятствий.
Допустимость: когда A* оптимален?
A* гарантирует оптимальный путь только если эвристика **допустимая** (admissible).
**Допустимая эвристика** - та, которая **никогда не переоценивает** реальное расстояние до цели:
**Почему это важно?**
Если h переоценивает, A* может 'подумать', что хороший путь плохой, и пропустить его:
**Примеры допустимых эвристик:**
• h(n) = 0 - всегда допустима (но A* вырождается в Dijkstra)
• Манхэттен для 4-связной сетки - допустима (точно равна минимальному пути без препятствий)
• Евклид для любого графа - допустима (прямая всегда ≤ любого пути)
**Чем ближе h к реальному расстоянию, тем быстрее A*:**
Если нужна скорость важнее оптимальности, можно использовать Weighted A*: f = g + w×h, где w > 1. Путь будет не более чем в w раз длиннее оптимального.
Что произойдёт, если эвристика переоценивает расстояние?
Переоценивающая эвристика может 'отпугнуть' A* от хороших путей, заставив его выбрать более длинный маршрут.
Реализация A*
A* очень похож на Dijkstra. Главное отличие - приоритет в очереди: f = g + h вместо просто g.
**Оптимизации для продакшена:**
1. **Использовать бинарную кучу** вместо сортировки массива - O(log n) вставка/извлечение вместо O(n log n)
2. **Tie-breaking**: при равных f выбирать большее g (ближе к цели)
3. **Bidirectional A***: искать с двух сторон, встречаться посередине
4. **Jump Point Search (JPS)**: для uniform-cost сеток, пропускает симметричные пути
Сложность A*: O(b^d) в худшем случае, где b - branching factor, d - глубина. Но на практике хорошая эвристика сильно сокращает это.
A* с идеальной эвристикой (h* = h) найдёт оптимальный путь быстрее, чем Дейкстра, при любом графе
Только при условии, что h допустима (не переоценивает). Идеальная h* ускоряет поиск, но если граф имеет одинаковые веса рёбер - A* и Дейкстра сходятся к одному поведению
Гарантия оптимальности A* зависит от допустимости, а не от точности h. Переоценивающая эвристика даёт более быстрый (но не оптимальный) поиск
Чем A* отличается от Dijkstra в реализации?
Единственное существенное отличие - приоритет в очереди: Dijkstra использует g (расстояние от старта), A* использует f = g + h (+ оценка до цели).
Итоги
- A* = Dijkstra + эвристика
- f(n) = g(n) + h(n): g - пройденный путь, h - оценка оставшегося
- Допустимая эвристика (h ≤ реального) гарантирует оптимальность
- Манхэттен для 4-связной сетки, Евклид для произвольного движения
Вопросы для размышления
- Дан граф с отрицательными весами рёбер. Почему ни A*, ни Дейкстра не подходят, и какой алгоритм нужен?
Связи с другими алгоритмами
A* обобщает Dijkstra и BFS с помощью эвристики
Связанные уроки
- alg-14-dijkstra — A* - это Dijkstra, направляемый эвристикой
- alg-12-bfs — A* без весов вырождается в BFS
- alg-32-branch-bound — Оба отсекают поиск оптимистичными границами
- ds-14-heaps-intro — A* достаёт узел с минимальным f-score из кучи
- ml-48-rl-intro