Пошук 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*, але може коштувати вам найдешевшого шляху.