A*: как найти кратчайший путь в лабиринте

Посмотрите A* по шагам на сайте: https://grundyjs.ru/algorithms/a-star-search/?utm_source=rutube&utm_medium=social&utm_campaign=a_star_search&utm_content=horizontal A* выбирает клетку с минимальным f = g + h. g — длина лучшего пока найденного пути от старта, h — манхэттенская оценка до цели без учёта стен. На том же лабиринте 7 × 4 жадный поиск находит маршрут из 10 переходов, а A* — из 8. В ролике разбираем выбор из всей границы поиска, тупик рядом с выходом и восстановление пути по предкам. В этой сетке движения разрешены по четырём направлениям и каждый проход стоит единицу. Манхэттенская эвристика согласованна, поэтому A* гарантирует кратчайший путь. На сайте можно пройти алгоритм по шагам, менять скорость и проверить случай, когда старт совпадает с целью. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #лабиринт #AStar #программирование