Короткий или дешёвый? BFS, Дейкстра и A* на одном лабиринте

Интерактивное сравнение BFS, Дейкстры и A*: https://grundyjs.ru/algorithms/weighted-maze-search/?utm_source=rutube&utm_medium=social&utm_campaign=weighted_maze_search&utm_content=horizontal Один взвешенный лабиринт, одинаковые старт и выход — три правила выбора следующей клетки. Синий BFS ищет минимум по числу переходов и не учитывает цену клеток. Жёлтый алгоритм Дейкстры выбирает минимальную известную стоимость от старта. Фиолетовый A* добавляет к ней оценку оставшегося пути: расстояние по горизонтали и вертикали без учёта стен, умноженное на минимальную цену шага. Результаты исходной карты: • BFS: 16 переходов, стоимость 22, обработано 76 клеток. • Дейкстра: 18 переходов, стоимость 18, обработано 62 клетки. • A*: 18 переходов, стоимость 18, обработана 31 клетка. Больше переходов, зато дешевле. При единичных весах стоимость равна числу переходов: все три поиска находят путь из 16 переходов стоимостью 16. Ветви одной волны показаны одновременно, исчерпанные тупики сереют. У алгоритмов разные приоритеты; длительность анимации не измеряет быстродействие программы. На другой карте преимущество A* по числу обработанных клеток может измениться. В интерактивном разборе меняйте цену клетки, проходите поиск по шагам и сравнивайте результаты. Авторская озвучка. Музыки нет. #алгоритмы #BFS #Дейкстра #AStar #программирование