Что такое A* и как эвристика ускоряет поиск пути по сравнению с Дейкстрой?
Ищу путь на большой сетке из одной точки в другую. Дейкстра честно находит, но обходит кучу лишних клеток во все стороны. Слышал про A* с эвристикой — как он отличается от Дейкстры и почему быстрее? Когда он точно даёт верный ответ?
2 ответа
A* — это Дейкстра, в которой приоритет вершины в куче не dist[v], а dist[v] + h(v), где h(v) — эвристика, оценка оставшегося расстояния от v до цели. Это направляет поиск «в сторону цели», а не во все стороны равномерно, поэтому A* раскрывает гораздо меньше вершин.
Дейкстра берёт ближайшую по dist. A* берёт ту, что выглядит ближе к цели в сумме. На сетке типичная h — манхэттенское или евклидово расстояние до финиша.
Корректность: A* находит оптимум, если эвристика допустима (h(v) никогда не переоценивает реальное оставшееся расстояние) — и тогда A* эквивалентен Дейкстре с потенциалами. Если ещё и монотонна (consistent: h(u) <= w(u,v) + h(v)), то каждая вершина раскрывается один раз, как в обычной Дейкстре.
Сложность в худшем случае та же — O(E log V), выигрыш на практике за счёт меньшего числа раскрытых вершин.
Важная грань: если h(v) = 0 для всех вершин — A* вырождается в Дейкстру (никакой направленности). Если h переоценивает (недопустима) — A* быстрее, но может вернуть НЕ кратчайший путь. На олимпиадах A* встречается редко (его сложно гарантированно уложить в лимит, эвристику не всегда придумаешь), чаще он в геймдеве/робототехнике. Для контеста почти всегда достаточно Дейкстры или 0-1 BFS.