Порівняйте алгоритми пошуку шляху у реальному часі: A* з евристикою, Дейкстру для гарантовано найкоротшого шляху та BFS для незваженого графу. Малюйте перешкоди і дивіться, як вони справляються.
A* поєднує реальну вартість g(n) з евристичною оцінкою h(n) майбутньої вартості: f(n) = g(n) + h(n). З допустимою евристикою A* гарантовано оптимальний. Дейкстра — особливий випадок A* без евристики.
Розставляйте перешкоди, початкову та кінцеву точки. Виберіть алгоритм і дивіться, як поширюється пошук. Порівняйте кількість відвіданих вузлів для кожного алгоритму.
A* використовується в мільйонах відеоігор і Google Maps. Сучасний навігаційний алгоритм Google обробляє мільйони вузлів — але суть та сама: f(n) = g(n) + h(n), придумана у 1968 р.