Лабиринт GrundyJS.ru: четыре алгоритма одновременно | 20 минут

Интерактивная генерация лабиринта и сравнение BFS/DFS: https://grundyjs.ru/algorithms/maze/?utm_source=rutube&utm_medium=social&utm_campaign=maze&utm_content=brand_maze_horizontal Один лабиринт в форме GrundyJS.ru, общий вход и выход и четыре поиска, которые постепенно закрашивают надпись. На совпадающих участках их цвета смешиваются. В самом видео нет подписей и счётчиков — только прохождение. Без озвучки и музыки. Цвета, правила и результаты именно на этом лабиринте: Голубой — BFS, поиск в ширину. Использует очередь и расширяет поиск по слоям расстояния от старта. Обработано 3 100 клеток; найденный путь — 850 переходов. Оранжевый — DFS, поиск в глубину. Идёт по одной ветке, хранит её в стеке и возвращается из тупиков. Обработано 1 856 клеток; путь — 960 переходов. Фиолетовый — жадный поиск, Greedy Best-First. Выбирает из границы поиска клетку с минимальной оценкой h до выхода, без учёта уже пройденного расстояния. Обработано 1 387 клеток; путь — 926 переходов. Зелёный — A*. Выбирает минимальное f = g + h: g — лучший найденный путь от старта до клетки, h — оценка оставшегося пути до выхода. Обработано 3 085 клеток; путь — 850 переходов. Каждый проход стоит единицу, движения разрешены по четырём направлениям. h — манхэттенское расстояние без учёта стен. При этих условиях BFS и A* находят кратчайший путь; DFS и Greedy в этом примере возвращают более длинные маршруты, обработав меньше клеток. Эти результаты не означают универсального преимущества на других лабиринтах. Ветви BFS одного слоя и независимые готовые ветви A* с одинаковым f показаны одновременно. Порядок трассы сохранён: дочерняя клетка ждёт завершения группы родителя. Темп выбран для визуализации и не является замером времени CPU. После нахождения выхода каждый поиск останавливается; непосещённые клетки остаются тёмными. Форма букв взята из векторного логотипа сайта; части надписи соединены узкими проходами. Лабиринт связный, содержит 3 150 клеток и циклы. Seed: 20261030. 00:00 Одновременный поиск 08:55 Greedy находит выход 11:53 DFS находит выход 19:35 Финиш BFS и A* #лабиринт #алгоритмы #BFS #DFS #astar