Кратко — почему застревает и как это исправить.
Проблема
- Исходные правила:
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- ancestor(X,Z), parent(Z,Y).
- При поиске Prolog использует глубинный поиск слева направо (SLD): во второй клаузе первая цель — рекурсивный вызов $ancestor(X,Z)$. Чтобы доказать её, интерпретатор снова применяет ту же вторую клаузу и сразу опять пытается доказать новый $ancestor(X,...)$ — и так бесконечно (лёгкая леворекурсивная бесконечность), потому что рекурсия не «сужает» цель до факта parent перед рекурсивным развёртыванием.
Как исправить (практически и безопасно)
1) Поменять порядок литералов (правила правой рекурсии):
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
Объяснение: сначала проверяется конкретный факт parent(X,Z) — это даёт конкретные Z и порождает конечные цепочки, а затем рекурсивный вызов идёт «вглубь» по уже уменьшенному пространству поиска.
2) Использовать таблирование (memoization), если среда поддерживает (XSB, SWI-Prolog: `:- table ancestor/2.`):
- Гарантирует завершение для конечных графов предков, устраняет повторные вычисления и циклы.
3) Использовать ограничение глубины / итеративное углубление:
- Для больших/потенциально бесконечных графов можно выполнять поиск с ограничением глубины и постепенно увеличивать глубину.
4) Аккумулятор / явный путь (если нужно избегать повторений и циклов):
- Ввести вспомогательный предикат с аккумулятором посещённых узлов, чтобы не возвращаться по циклам:
ancestor(X,Y) :- ancestor_acc(X,Y,[X]).
ancestor_acc(X,Y,_) :- parent(X,Y).
ancestor_acc(X,Y,Visited) :-
parent(X,Z),
\+ member(Z,Visited),
ancestor_acc(Z,Y,[Z|Visited]).
- Это предотвращает бесконечные циклы в графах с петлями.
5) Жёсткая обрезка (cut) и once/1 — осторожно:
- Например `ancestor(X,Y) :- parent(X,Y), !.` — убирает альтернативы после первого успеха, но может потерять другие правильные решения, поэтому применять только при уверенности в семантике.
Общие приёмы управления откатом и порядком правил
- Ставьте «сужающие» (детерминирующие) предикаты раньше рекурсивных — это уменьшает дерево поиска.
- Избегайте левой рекурсии в средах с глубинным поиском, если она не сопровождается внешним ограничением.
- Используйте таблирование, если доступно — оно часто решает проблемы с циклами и повторными вычислениями.
- Применяйте аккумуляторы и проверку посещённых узлов для графов с циклами.
- Применяйте cut/once только когда точно нужна потеря альтернатив — это изменяет логическую семантику.
- Следите за индексированием аргументов фактов (порядок аргументов в parent/2 влияет на быстродействие).
Итого: самый простой и обычно правильный шаг — заменить вторую строку на правую рекурсию
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
или включить таблирование для гарантий завершения.