Пошук A*
Дейкстра з відчуттям напрямку. До вартості кожного місця він додає оцінку вартості, що лишилася, тому спершу пробує місця, які здаються найближчими до цілі.
- час O((V + E) log V)
- пам'ять O(V)
- черга з пріоритетом
Черга з пріоритетом: черга, де першим іде найдешевший, а не той, хто прийшов першим.
Інші терміни на цій сторінці
- Вартість: скільки коштує хід. У лабіринті земля коштує 1, бруд 3, вода 9; у графі — число на ребрі.
- Оцінка (h): припущення про вартість, що лишилася. A* лишається точним, лише якщо оцінка ніколи не завищена.
- Релаксація ребра: перевірка, чи шлях через поточне місце дає сусідові меншу вартість, і якщо так — її прийняття.
Спробуйте: Виберіть відкрите поле й перемикайтеся між Дейкстрою та A*: обидва знаходять шлях однакової вартості, але A* бере з черги значно менше клітинок.
Як це працює
A* працює як Дейкстра, але впорядковує чергу за f = вартість досі + h, де h оцінює вартість, що лишилася. У лабіринті h — кількість ходів до M без урахування стін і бруду; у графі — відстань по прямій, поділена на 10. Поки h ніколи не завищує, шлях, який має A* у момент узяття цілі, найдешевший, точно як у Дейкстри. Що краща оцінка, то менше місць треба переглянути.
Коли варто використовувати
A* потрібен, коли ви шукаєте одну ціль і можете оцінити, як далеко вона: пошук шляху в іграх, роботи, планувальники маршрутів на карті. За h = 0 це рівно Дейкстра. Оцінка, яка може завищувати, пришвидшує A*, але може коштувати вам найдешевшого шляху.