Алгоритми пошуку шляху
Задача: знайти шлях від старту до фінішу в графі (тут — сітка клітинок). Алгоритми відрізняються тим, яку вершину розглядати наступною.
Огляд
- BFS (пошук ушир): черга; розширюється хвилями. Знаходить найкоротший шлях за кількістю кроків, але ігнорує вартість клітинок.
- DFS (пошук углиб): стек; «пірнає» якомога глибше. Знаходить якийсь шлях, зазвичай довгий і звивистий.
- Дейкстра: пріоритетна черга за вартістю g від старту. Знаходить мінімальну вартість (враховує болото ×5), але досліджує «всюди».
- A*: пріоритет f = g + h, де h — оцінка відстані до цілі (евристика). Знаходить оптимальний шлях, досліджуючи значно менше клітинок.
- Жадібний (greedy best-first): пріоритет лише h — швидкий, але не гарантує оптимальності.
Евристика
h = |x₁ − x₂| + |y₁ − y₂| (Манхеттен, 4 напрями)
h = max(dx, dy) + (√2 − 1)·min(dx, dy) (8 напрямів)
Допустима евристика (ніколи не переоцінює) гарантує оптимальність A*. Повзунок «вага евристики» у A* перетворює його: 0 → Дейкстра, 1 → A*, велика → майже жадібний.
Де застосовують
Навігатори, ШІ ворогів у іграх, маршрутизація мережевих пакетів, робототехніка, планування рухів маніпуляторів.
Спробуйте
- Порівняйте число досліджених клітинок A* і Дейкстри на порожньому полі.
- Поставте стіну-«підкову» між стартом і фінішем: де жадібний пошук застряє?
- Додайте болото: BFS іде крізь нього, Дейкстра і A* — обходять.