Алгоритм A* (А-звездочка): Интеллектуальный поиск пути
Алгоритм Дейкстры гарантированно находит кратчайший путь на графе, но он делает это "вслепую". Дейкстра исследует все возможные направления во все стороны (подобно кругам на воде), пока случайно не наткнется на финишную точку. Это крайне неэффективно для навигационных систем и компьютерных игр, где персонажу нужно дойти из точки А в точку Б на огромной карте. В 1968 году Питер Харт, Нильс Нильсон и Бертрам Рафаэль разработали алгоритм A* — вершину эволюции алгоритмов поиска пути.
Алгоритм A* (произносится "А-звездочка") комбинирует математическую строгость алгоритма Дейкстры с целенаправленностью метода Жадного наилучшего поиска (Greedy Best-First Search). Секретное оружие A* — это эвристическая функция H(n).
В процессе работы алгоритм оценивает каждый узел-кандидат (n) на карте с помощью оценочной функции F(n) = G(n) + H(n), где:
- G(n) — это точная стоимость пути от стартовой точки до текущего узла n (как в алгоритме Дейкстры).
- H(n) — это эвристика: примерная, математически вычисленная стоимость пути от узла n до финиша.
- F(n) — итоговая оценка узла. Алгоритм всегда извлекает из приоритетной очереди узел с минимальным значением F(n).
Вектор направления задает именно H(n). Например, если мы ищем путь на сетке (квадратной карте), мы можем использовать Манхэттенское расстояние (сумма модулей разности координат X и Y) или Евклидово расстояние (прямая линия). Эвристика как бы "тянет" алгоритм в сторону цели, заставляя его в первую очередь проверять те клетки, которые физически ближе к финишу, игнорируя тупиковые ответвления в противоположной стороне.
Важнейшая теорема дискретной математики гласит, что A* гарантированно найдет оптимальный (наикратчайший) путь, если эвристическая функция H(n) является допустимой (admissible). Это означает, что эвристика никогда не должна переоценивать реальное расстояние до цели. Она может недооценить его (например, посчитать расстояние по прямой, хотя на пути стоит стена, которую придется обходить), но не может выдать число больше реального. Если H(n) всегда равна нулю, то A* полностью деградирует до алгоритма Дейкстры.
Алгоритм A* является абсолютным стандартом индустрии GameDev. Движение юнитов в стратегиях (StarCraft, Warcraft), навигация NPC в открытых мирах — всё это работает на основе модификаций A* (таких как IDA* или Jump Point Search), работающих поверх навигационных сеток (NavMesh). Этот алгоритм — идеальный пример того, как добавление простой геометрической логики в абстрактную теорию графов экономит миллионы тактов процессора.
