Алгоритм A*

Алгоритм A\ (произносится «А звезда» или «А стар») — это алгоритм поиска кратчайшего пути на графе, широко применяемый в информатике, робототехнике и разработке компьютерных игр. Он относится к классу информированных алгоритмов поиска, так как использует эвристическую функцию для оценки стоимости пути от текущей вершины до цели. A является обобщением алгоритма Дейкстры, в который добавлена эвристическая составляющая, что позволяет ему находить оптимальный путь значительно быстрее при условии, что эвристика является допустимой (не переоценивает реальную стоимость).

История

Алгоритм A был впервые описан в 1968 году группой исследователей Стэнфордского исследовательского института (SRI International) — Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Работа была опубликована в статье «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» в журнале IEEE Transactions on Systems Science and Cybernetics. Разработка велась в рамках проекта Shakey, целью которого было создание мобильного робота, способного планировать свои действия в реальном мире. Название алгоритма происходит от обозначения, использованного в статье: «A» (A с индексом звёздочка) — как символ оптимальности среди всех алгоритмов класса A.

Принцип работы

A* работает на взвешенном графе, где каждому ребру присвоена стоимость перехода. Алгоритм находит путь от начальной вершины к целевой, минимизируя суммарную стоимость. Основная идея заключается в комбинировании двух оценок:

• g(n) — фактическая стоимость пути от начальной вершины до вершины n.
• h(n) — эвристическая оценка стоимости пути от вершины n до цели.

Функция оценки f(n) = g(n) + h(n) определяет приоритет вершины для обработки. Алгоритм поддерживает два множества: открытое (вершины, которые нужно исследовать) и закрытое (уже исследованные вершины). На каждом шаге из открытого множества выбирается вершина с наименьшим f(n), затем она исследуется, и её соседи добавляются в открытое множество.

Псевдокод

``` function A*(start, goal) openSet = {start} cameFrom = empty map gScore[start] = 0 fScore[start] = h(start)

while openSet is not empty current = vertex in openSet with lowest fScore if current == goal return reconstruct_path(cameFrom, current)

openSet.remove(current) for each neighbor of current tentative_gScore = gScore[current] + d(current, neighbor) if tentative_gScore < gScore[neighbor] cameFrom[neighbor] = current gScore[neighbor] = tentative_gScore fScore[neighbor] = gScore[neighbor] + h(neighbor) if neighbor not in openSet openSet.add(neighbor)

return failure ```

Свойства

Допустимость и оптимальность

A* гарантированно находит оптимальный путь, если эвристическая функция h(n) является допустимой, то есть никогда не переоценивает истинную стоимость пути до цели. Для евклидовых пространств часто используется евклидово расстояние или манхэттенское расстояние (для сеток с четырёхсторонним движением).

Монотонность (согласованность)

Эвристика называется монотонной (или согласованной), если для любых двух вершин u и v выполняется неравенство: h(u) ≤ d(u,v) + h(v), где d(u,v) — стоимость ребра между ними. Для монотонных эвристик A* не требует повторного открытия вершин, что ускоряет работу.

Сложность

Временная сложность A* зависит от качества эвристики. В худшем случае (при плохой эвристике) она экспоненциальна. В лучшем случае, когда эвристика идеальна (h(n) = истинная стоимость), сложность линейна по длине пути. В среднем, для задач с хорошей эвристикой, сложность полиномиальна.

Эвристические функции

Выбор эвристики критически влияет на производительность A*. Основные типы эвристик:

• Манхэттенское расстояние — для сеток с четырёхсторонним движением: |x1-x2| + |y1-y2|.
• Евклидово расстояние — для непрерывных пространств: sqrt((x1-x2)^2 + (y1-y2)^2).
• Чебышёвское расстояние — для сеток с восьмисторонним движением: max(|x1-x2|, |y1-y2|).
• Октаэдрическое расстояние — для трёхмерных сеток.

Применение

Компьютерные игры

A является стандартом для поиска пути в играх. Он используется в стратегиях реального времени (StarCraft, Warcraft), ролевых играх (The Elder Scrolls, Fallout) и шутерах. В играх часто применяются оптимизации: иерархический A, разбиение карты на области, предварительные вычисления.

Робототехника

В мобильной робототехнике A используется для планирования траекторий в известной среде. Роботы с лазерными дальномерами или камерами строят карту и применяют A для навигации. В реальном времени часто используют D (Dynamic A) — вариант для динамически меняющейся среды.

Геоинформационные системы

В навигационных приложениях (Яндекс.Карты, 2ГИС, Google Maps) A* лежит в основе расчёта маршрутов. Для дорожных сетей применяются модификации с иерархическими графами (Contraction Hierarchies).

Логистика

В системах управления складом и транспортной логистике A* используется для оптимизации маршрутов погрузчиков, дронов и курьеров.

Модификации

A* с повторным открытием

В некоторых реализациях, если найдена вершина с меньшим g(n), она повторно открывается. Это необходимо для недопустимых эвристик.

Итеративное углубление A (IDA)

Вариант, использующий ограничение по f-стоимости. На каждой итерации увеличивается порог, что позволяет работать с ограниченной памятью.

Двунаправленный A*

Поиск одновременно от начальной и целевой вершин. Требует согласования эвристик и может быть эффективнее для больших графов.

Weighted A (Взвешенный A)

Использует весовой коэффициент w > 1 для эвристики: f(n) = g(n) + w * h(n). Это ускоряет поиск, но теряет гарантию оптимальности.

Критика и ограничения

• Требования к памяти: A* хранит все исследованные вершины, что может быть проблематично для больших графов.
• Чувствительность к эвристике: плохая эвристика приводит к экспоненциальному росту времени.
• Неприменимость к непрерывным пространствам: требуется дискретизация, что может вызывать ошибки.
• Статичность: классический A неэффективен при динамических изменениях среды (для этого существуют D и Lifelong Planning A*).

Интересные факты

• Алгоритм A* является частным случаем алгоритма Дейкстры, если h(n) = 0 для всех вершин.
• В 2012 году алгоритм A* был включён в список «10 алгоритмов, оказавших наибольшее влияние на развитие науки и техники» по версии журнала IEEE Spectrum.
• Название «A*» было выбрано потому, что авторы хотели обозначить «оптимальный алгоритм A» — звездочка символизировала оптимальность среди всех алгоритмов класса A.
• В компьютерных играх A* часто реализуется на языке C++ с использованием приоритетных очередей (heap) для ускорения выбора вершины с минимальным f(n).

Источники

• Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). «A Formal Basis for the Heuristic Determination of Minimum Cost Paths». IEEE Transactions on Systems Science and Cybernetics.
• Russell, S. J.; Norvig, P. (2020). «Artificial Intelligence: A Modern Approach» (4th ed.). Pearson.
• LaValle, S. M. (2006). «Planning Algorithms». Cambridge University Press.
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2009). «Introduction to Algorithms» (3rd ed.). MIT Press.