Жадный поиск (Greedy Best-First)

Оценка расстояния, а не готовый маршрут

Эвристика h — манхэттенское расстояние: |столбец − столбецЦели| + |строка − строкаЦели|. Перемещения разрешены на север, восток, юг и запад, каждое стоит единицу. Оценка игнорирует стены: клетка рядом с целью может оказаться тупиком. S обозначает старт, G — цель.

Для такой сетки h не завышает кратчайшее оставшееся расстояние. Но даже допустимая эвристика не делает Greedy оптимальным: он сравнивает только h и игнорирует уже пройденное расстояние g.

Выбираем из всей границы поиска

Граница поиска содержит обнаруженные клетки, которые ещё не извлекали. Извлекаем клетку с минимальным h; если это цель, останавливаемся. Иначе проверяем открытые проходы в порядке север/восток/юг/запад и добавляем новых соседей. При одинаковом h раньше выбирается раньше обнаруженная клетка.

Отмечаем клетку при добавлении и сохраняем первого предка. Каждая клетка входит в границу поиска не более одного раза. Поэтому циклы не мешают завершению: в конечном лабиринте поиск найдёт маршрут, если тот существует. Выбор клетки не означает физический переход из предыдущей: поиск может переключаться между ветками.

Ближе к цели, но длиннее по маршруту

Координаты (столбец, строка) начинаются с 1. Из S=(1,3) восточный сосед имеет h=5, а южный — h=7. Greedy идёт на восток, доходит до (6,3) с h=1 и упирается в стену. Затем возвращается к ожидающим клеткам и исследует верхний проход.

Полученный маршрут содержит 10 рёбер. Нижний путь через четвёртую строку требует только 8. В лабиринте специально оставлен цикл, чтобы можно было сравнить разные маршруты. Минимальная оценка не гарантирует кратчайший ответ. Зелёный путь восстанавливается по предкам, а не по порядку извлечения клеток.

Что считают счётчики

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

При восстановлении зелёный путь растёт от цели к старту; в итоговом снимке порядок разворачивается. Непосещённые после успеха клетки ещё не исследованы, но не обязательно недостижимы. Перезапуск и перемотка используют сохранённые неизменяемые состояния. Во втором примере старт совпадает с целью: одно извлечение и путь длиной ноль.

Стоимость этой реализации

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

Плеер сохраняет до O(V) снимков с O(V) данными клеток в каждом: история визуализации занимает O(V²) памяти плюс общий граф. Это стоимость перемотки, а не самого поиска. Порядок при равных оценках детерминирован; это правило разрешения равенств, а не устойчивость сортировки.

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

Код принимает Map от id клеток к упорядоченным массивам соседей, существующие id старта и цели и конечную неотрицательную эвристику h. Значение null нельзя использовать как id. Для поведения плеера стройте соседей из открытых проходов в порядке С/В/Ю/З и используйте манхэттенскую h. Вход не меняется; null означает отсутствие пути. Плеер дополнительно проверяет и копирует лабиринт.

function greedyBestFirst(adjacency, start, goal, h) {
    const open = [start];
    const parent = new Map([[start, null]]);
    while (open.length) {
        let best = 0;
        for (let i = 1; i < open.length; i++) {
            if (h(open[i]) < h(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();
        }
        for (const next of adjacency.get(current)) {
            if (parent.has(next)) continue;
            parent.set(next, current);
            open.push(next);
        }
    }
    return null;
}

От Greedy к A*

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