Пути в графе

Урок о том, как описать граф фактами и рекурсивно искать пути, не зациклившись на циклах самого графа.

Путь в графе — последовательность узлов, в которой каждая соседняя пара соединена ребром; в Prolog он строится рекурсивным предикатом поверх фактов о рёбрах.

Зачем это

Графы — повсюду: дороги между городами, ссылки между страницами, зависимости задач. Вопрос «можно ли добраться из A в B?» — это поиск пути. Prolog отвечает на него почти дословно: опишите рёбра фактами, а достижимость — рекурсивным правилом, и бэктрекинг сам переберёт маршруты. Этот урок собирает воедино бэктрекинг и рекурсию из предыдущих уроков и добавляет важный новый сюжет — борьбу с циклами.

Граф как факты

Ребро edge(a, b) означает «из a можно шагнуть в b» (ориентированный граф). Возьмём такой граф:

edge(a, b).
edge(b, c).
edge(c, d).
edge(a, e).
edge(e, d).

Картинка (стрелки чёрточками, без угловых скобок):

   a ---- b ---- c ---- d
   |                    |
   +------ e -----------+

Наивный path: достижимость

По аналогии с ancestor определим путь рекурсивно: из X в Y можно пройти, если есть прямое ребро, либо если есть ребро в промежуточный узел Z, из которого уже достижим Y.

path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

Спросим маршруты из a в d:

?- path(a, d).
true ;   % через b, c
true ;   % через e
false.

Два разных маршрута — два успеха через ;. Пока всё хорошо, потому что наш граф ациклический.

Проблема циклов

Добавим всего одно ребро, замыкающее цикл b → a:

edge(b, a).   % теперь a -- b -- a -- b -- ... цикл!

Запрос path(a, c) может уйти в бесконечность: a → b → a → b → … Prolog честно ходит по кругу, ведь правило не запрещает возвращаться в уже посещённый узел. Дерево поиска становится бесконечным:

path(a, c)
  edge(a, b), path(b, c)
    edge(b, a), path(a, c)      [вернулись в a!]
      edge(a, b), path(b, c)    [и снова...]
        ... бесконечный спуск

Базовый случай edge(b, c) существует, но Prolog до него может не добраться, застряв в петле a↔b. Наивный path небезопасен на графах с циклами.

Решение: список посещённых узлов

Идея проста: помним, где уже были, и не заходим туда повторно. Заведём третий аргумент Visited — список пройденных узлов. Перед шагом в новый узел проверяем, что его там ещё нет, предикатом \+ member(...) (\+ — «не доказуемо», отрицание).

% Внешний предикат: начинаем с уже посещённого старта.
path(X, Y) :- path(X, Y, [X]).

% База: дошли прямым ребром.
path(X, Y, _Visited) :- edge(X, Y).

% Шаг: идём в Z, которого ещё не было в Visited.
path(X, Y, Visited) :-
    edge(X, Z),
    \+ member(Z, Visited),
    path(Z, Y, [Z | Visited]).

Запись [Z | Visited] добавляет Z в голову списка посещённых. Теперь возврат в уже пройденный узел отсекается: \+ member(a, [b, a]) ложно, ветка a→b→a мгновенно проваливается, и бэктрекинг уводит поиск на другие рёбра. Даже с циклом b → a запрос path(a, c) завершается и находит путь a→b→c.

Собрать сам маршрут

Часто нужен не только ответ «да/нет», но и сам список узлов. Вернём накопленный путь четвёртым аргументом:

% Path -- список узлов от X до Y включительно.
route(X, Y, Path) :- route(X, Y, [X], Path).

route(X, Y, Visited, Path) :-
    edge(X, Y),
    reverse([Y | Visited], Path).

route(X, Y, Visited, Path) :-
    edge(X, Z),
    \+ member(Z, Visited),
    route(Z, Y, [Z | Visited], Path).

Мы накапливаем узлы в Visited в обратном порядке (новый — в голову), а в момент успеха разворачиваем список через reverse/2. Запрос находит все маршруты бэктрекингом (на исходном ациклическом графе):

?- route(a, d, P).
P = [a, b, c, d] ;
P = [a, e, d] ;
false.

Вывод:

P = [a, b, c, d] ;
P = [a, e, d] ;
false.

Как работает под капотом

Список Visited — это аккумулятор: параметр, который «растёт» по мере спуска рекурсии и несёт накопленное состояние. На каждом уровне он своя копия (как все переменные в рекурсии), поэтому при бэктрекинге к развилке восстанавливается прежнее, более короткое состояние — и Prolog честно перебирает альтернативные маршруты, не путая их между собой. Проверка \+ member(Z, Visited) превращает потенциально бесконечное дерево поиска в конечное: глубина пути ограничена числом узлов графа.

Частые ошибки

• Наивный path без Visited на графе с циклами — зацикливание и зависание. Всегда учитывайте, может ли граф содержать циклы.
• Забыть положить стартовый узел в Visited (вызвать path(X, Y, []) вместо [X]) — тогда можно вернуться в сам старт.
• Проверять member после рекурсивного вызова, а не до — проверку \+ member(Z, Visited) ставьте ПЕРЕД path(Z, ...), иначе отсечение не сработает вовремя и спуск всё равно уйдёт в цикл.
• Забыть reverse при сборке пути — узлы накапливаются в голову, поэтому без разворота получите маршрут задом наперёд.

Итог

• Граф удобно описывать фактами edge/2, а достижимость — рекурсивным path.
• Наивный path зацикливается на графах с циклами.
• Список Visited и проверка \+ member запрещают повторный заход и делают поиск конечным.
• Аккумулятор-список плюс reverse позволяют вернуть сам маршрут, а бэктрекинг перебирает все пути.
• Проверку «не были ли мы тут» ставьте до рекурсивного шага.