A* (A-star) — алгоритм поиска кратчайшего пути в графе, сочетающий принцип алгоритма Дейкстры с эвристической оценкой расстояния до цели. Разработан Питером Хартом, Нилсом Нильссоном и Бертрамом Рафаэлем в 1968 году. Является оптимальным и полным при допустимой (admissible) эвристике.
Принцип работы
A* оценивает каждую вершину v функцией f(v) = g(v) + h(v), где:
- g(v) — реальная стоимость пути от старта до v
- h(v) — эвристическая оценка расстояния от v до цели
- f(v) — полная оценка; алгоритм всегда расширяет вершину с минимальным f
Алгоритм сохраняет открытый список (вершины для рассмотрения, priority queue) и закрытый (уже обработанные). На каждом шаге берётся вершина с минимальным f, проверяются её соседи.
Требования к эвристике
- Admissible (допустимая) — h(v) никогда не переоценивает истинное расстояние: h(v) ≤ d*(v). Это гарантирует оптимальность пути
- Consistent (согласованная) — h(u) ≤ cost(u,v) + h(v) для любого ребра. Более сильное условие, гарантирует монотонность
Примеры эвристик: Евклидово расстояние √[(x₁−x₂)²+(y₁−y₂)²] для 2D-сетки, Манхэттенское расстояние |x₁−x₂|+|y₁−y₂| для движения по четырём направлениям.
Применение
A* — стандарт в игровом AI для нахождения пути персонажей. Используется в навигационных системах (Google Maps, Яндекс.Навигатор) вместе с иерархическими улучшениями. Применяется в робототехнике для планирования маршрутов. На больших графах используют A* с «jump point search» или bidirectional A* для ускорения.