Поиск A*
Дейкстра с чувством направления. К стоимости каждого места он прибавляет оценку оставшейся стоимости, поэтому сначала пробует места, которые кажутся ближе всего к цели.
- время O((V + E) log V)
- память O(V)
- использует очередь с приоритетом
Что это значит?
- Стоимость: сколько стоит ход. В лабиринте земля стоит 1, грязь 3, вода 9; в графе — число на ребре.
- Очередь с приоритетом: очередь, где первым идёт самый дешёвый, а не тот, кто пришёл первым.
- Оценка (h): предположение об оставшейся стоимости. A* остаётся точным, только если оценка никогда не завышена.
- Релаксация ребра: проверка, даёт ли путь через текущее место соседу меньшую стоимость, и если да — её принятие.
- в очереди
- текущая
- готова
- самый дешёвый путь
- земля · 1
- грязь · 3
- вода · 9
- стена
Новая: Старт в A1 со стоимостью 0 и оценкой 26 до цели. Он единственный в очереди.
Пробел: воспроизведение или пауза. Стрелки влево и вправо: шаг. Home и End: в начало или в конец.
Попробуйте: Выберите открытое поле и переключайтесь между Дейкстрой и A*: оба находят путь одинаковой стоимости, но A* берёт из очереди гораздо меньше клеток.
Как это работает
A* работает как Дейкстра, но упорядочивает очередь по f = стоимость до сих пор + h, где h оценивает оставшуюся стоимость. В лабиринте h — число ходов до M без учёта стен и грязи; в графе — расстояние по прямой, делённое на 10. Пока h никогда не завышает, путь, который есть у A* в момент взятия цели, самый дешёвый, точно как у Дейкстры. Чем лучше оценка, тем меньше мест нужно просмотреть.
Когда стоит применять
A* нужен, когда вы ищете одну цель и можете оценить, как далеко она: поиск пути в играх, роботы, планировщики маршрутов на карте. При h = 0 это ровно Дейкстра. Оценка, которая может завышать, ускоряет A*, но может стоить вам самого дешёвого пути.