Как использовать двунаправленное движение в алгоритмах обхода?

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

Как это работает

Алгоритм поддерживает две очереди (если используется BFS) и два набора посещённых вершин — по одному для каждого направления. На каждом шаге он расширяет вершину из очереди с меньшим размером (или по очереди), проверяя, не появилась ли текущая вершина в множестве посещённых вершин противоположного поиска. Если появилась — путь найден. Путь строится объединением пути от старта до точки встречи и пути от точки встречи до цели (в обратном порядке).

Преимущества и применение

• Эффективность по времени и памяти: В худшем случае сложность остаётся O(b^(d/2)), где b — коэффициент ветвления, а d — глубина цели. Это квадратный корень от сложности обычного BFS (O(b^d)), что даёт огромный выигрыш для больших графов.
• Типичные сценарии: Поиск кратчайшего пути в ненаправленных графах (например, в социальных сетях для поиска связей между людьми), решение головоломок (пятнашки), проверка связности в очень больших графах.

Пример кода (упрощённый BFS)

function bidirectionalBFS(graph, start, target) {
    if (start === target) return [start];

    // Очереди и посещённые узлы для двух направлений
    let queueStart = [start];
    let queueTarget = [target];
    let visitedStart = new Map(); // vertex -> parent
    let visitedTarget = new Map();
    visitedStart.set(start, null);
    visitedTarget.set(target, null);

    while (queueStart.length && queueTarget.length) {
        // Расширяем поиск от старта
        let meetingNode = expandLevel(graph, queueStart, visitedStart, visitedTarget);
        if (meetingNode) return constructPath(meetingNode, visitedStart, visitedTarget);

        // Расширяем поиск от цели
        meetingNode = expandLevel(graph, queueTarget, visitedTarget, visitedStart);
        if (meetingNode) return constructPath(meetingNode, visitedStart, visitedTarget);
    }
    return null; // Путь не найден
}

function expandLevel(graph, queue, visitedFrom, visitedOpposite) {
    let vertex = queue.shift();
    for (let neighbor of graph[vertex]) {
        if (!visitedFrom.has(neighbor)) {
            visitedFrom.set(neighbor, vertex);
            // Проверка встречи
            if (visitedOpposite.has(neighbor)) return neighbor;
            queue.push(neighbor);
        }
    }
    return null;
}
// Функция constructPath собирает итоговый путь из двух половин.

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