Где применяется
1. Задача
У тебя есть карта-сетка. Часть клеток открыта, по ним можно ходить. Остальные клетки это стены. Ты стоишь на стартовой клетке, и тебе нужна одна конкретная клетка-цель. Ходить можно вверх, вниз, влево и вправо. Нужно наименьшее число шагов до цели.
BFS по сетке (шаг 90) и Дейкстра (шаг 97) решают эту задачу, но расходятся вслепую во все стороны. Пусть цель далеко на востоке. Они всё равно так же старательно идут на запад, север и юг и проверяют тысячи клеток, которые никогда не понадобятся. На большой карте это медленно.
A* убирает лишнюю работу. Это Дейкстра с одной добавкой: для каждой клетки он оценивает, сколько от неё ещё осталось до цели. Эта оценка ведёт поиск в сторону цели. Поэтому A* открывает намного меньше клеток и получает тот же кратчайший ответ.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Кратчайший путь по сетке или по доске головоломки, когда известно, где цель. LeetCode принимает на них и обычный BFS, а A* с оценкой расстояния, которая никогда не завышает, даёт тот же ответ и открывает меньше клеток.
Здесь ходить можно в 8 сторон, поэтому замени манхэттенскую оценку урока на большее из расстояний по строкам и по столбцам.
Каждое состояние доски это вершина, а сумма манхэттенских расстояний плиток до их мест никогда не завышает число оставшихся ходов.
Ты идёшь от дерева к дереву по возрастанию высоты, и каждый переход это один поиск A* по сетке леса.