Поиск A*

Два расстояния — один приоритет

g — длина лучшего пока найденного пути от S до клетки. h — манхэттенская оценка до G: |столбец − столбецЦели| + |строка − строкаЦели|, без учёта стен. Сумма f = g + h оценивает длину всего маршрута через эту клетку. Это ещё не готовый путь.

В начале g(S)=0, у остальных клеток — бесконечность. Фиолетовая граница поиска содержит обнаруженные, ещё не извлечённые клетки. Выбираем минимальное f из всей границы; при равенстве раньше выбираем раньше обнаруженную клетку. Соседей смотрим в порядке север, восток, юг, запад. Поиск может переключаться между ветками: выбор клетки не означает физический переход из предыдущей.

Более короткий путь меняет предка

Для соседа через открытый проход пробуем candidate = g(текущая) + 1. Если это меньше сохранённого g, обновляем расстояние и предка. Новую клетку добавляем в границу поиска; уже ожидающая остаётся на месте с новым приоритетом. При равной длине сохраняем прежнего предка. Такое улучшение называют релаксацией.

Просто заменить h на g+h в Greedy с первым найденным предком недостаточно. Сначала до клетки может обнаружиться длинный путь, а затем более короткий. Здесь эвристика согласованная, поэтому у извлечённой для обработки клетки расстояние уже кратчайшее и повторно открывать её не нужно.

Восемь переходов вместо десяти

Перед нами тот же лабиринт 7×4, что в выпуске про Greedy. Координаты (столбец, строка) начинаются с 1. S=(1,3), G=(7,3). У восточного соседа g=1, h=5, f=6; у южного — g=1, h=7, f=8. A* тоже начинает справа и в итоге встречает тупик рядом с целью.

Верхний обход поднимает оценку до 10. У нижней ветки остаются клетки с f=8, и A* выбирает их раньше. Итоговый путь проходит по четвёртой строке и содержит 8 переходов; верхний маршрут Greedy — 10. Зелёный путь восстанавливается по предкам, а не по порядку обработки клеток. Пример показывает выбор по приоритету; не каждый вид релаксации обязательно встречается в этом обходе.

Почему путь здесь кратчайший

Каждый проход стоит единицу, движения разрешены по четырём направлениям, лабиринт конечный. Манхэттенская h равна нулю у цели, не завышает оставшийся путь и согласованна: для любого прохода u→v выполняется h(u) ≤ 1 + h(v). Оценку получаем, убрав стены; возвращение стен не может сократить маршрут.

При этих условиях закрытую клетку не нужно открывать заново. Завершаем поиск, когда цель извлечена с минимальным f, а не при первом обнаружении. Тогда A* возвращает кратчайший путь либо сообщает, что пути нет, если граница опустела. При несогласованной эвристике версия без повторного открытия может потерять эту гарантию. Для диагональных ходов, весов рёбер и других эвристик условия и код нужно пересмотреть.

Как читать плеер

Числа в клетках показывают f; бесконечность означает, что клетка ещё не обнаружена. S и G сохраняют свои обозначения. Под лабиринтом приведено g+h=f для текущей клетки и всей границы поиска. Фиолетовый цвет обозначает границу, рамка — текущую клетку, зелёный — восстановленный маршрут.

«Обнаружено» включает S и каждое первое добавление; «извлечено» считает выбор из границы, включая цель. «Просмотров соседей» учитывает открытые записи смежности, даже уже известных соседей; стены и соседи цели не входят в счётчик. «Улучшений пути» считает уменьшения уже конечного g. При восстановлении путь растёт от цели к старту, затем разворачивается в итоговом снимке. Попробуйте шаги, перемотку и пример с нулевым путём, когда старт совпадает с целью.

Стоимость этой версии

Для V клеток и E проходов реализация на массиве требует O(V² + E) времени и O(V) дополнительной рабочей памяти без хранения графа. Каждая клетка извлекается не более одного раза; поиск и удаление минимума стоят O(V), релаксация — O(1) на соседа. Бинарная куча с уменьшением ключа позволяет получить O((V+E) log V); здесь ради наглядности используется просмотр массива.

Для перемотки сохраняем полный снимок размером O(V) на каждом видимом событии. Событий O(V+E); в сетке с четырьмя соседями E=O(V), поэтому история занимает O(V²) памяти плюс общий лабиринт. Стоимость алгоритма и хранения визуализации различается.

Реализация на JavaScript

Код принимает конечный Map от id к упорядоченным массивам соседей, существующие id старта и цели, единичную стоимость рёбер и конечную неотрицательную согласованную h с h(цель)=0. Id не может быть null. Для повторения примера используйте открытые проходы в порядке С/В/Ю/З и манхэттенскую h. Вход не меняется; null означает отсутствие пути. Эта версия не поддерживает произвольные веса и не открывает закрытые вершины заново.

function aStar(adjacency, start, goal, h) {
    const open = [start];
    const closed = new Set();
    const g = new Map([[start, 0]]);
    const parent = new Map([[start, null]]);
    const f = v => g.get(v) + h(v);
    while (open.length) {
        let best = 0;
        for (let i = 1; i < open.length; i++) {
            if (f(open[i]) < f(open[best])) best = i;
        }
        const current = open.splice(best, 1)[0];
        if (current === goal) {
            const path = [];
            for (let v = goal; v !== null; v = parent.get(v)) path.push(v);
            return path.reverse();
        }
        closed.add(current);
        for (const next of adjacency.get(current)) {
            if (closed.has(next)) continue;
            const candidate = g.get(current) + 1;
            if (candidate >= (g.get(next) ?? Infinity)) continue;
            const unseen = !g.has(next);
            g.set(next, candidate);
            parent.set(next, current);
            if (unseen) open.push(next);
        }
    }
    return null;
}