Кратко — как работает резолюция (SLD) на вашем примере, где и почему может быть зацикливание, и как улучшить программу для эффективного поиска.
1) Как работает резолюция (пошагово)
- Пролог выбирает левую (первую) цель в текущем списке целей и пытается унифицировать её с головой некоторого правила/факта; при успешной унификации цель заменяется телом правила (после применения подстановки). Если дальнейший поиск терпит неудачу, происходит откат (backtrack) к следующей подходящей клаузуле и т. д.
Пример запроса: ?- ancestor(john,sue).
- Сначала пробует первый вариант правила (база): ancestor(X,Y) :- parent(X,Y).
унификация даёт ${\theta }_1=\{X/john,Y/sue\}$. Новая цель: parent(john,sue) — неудача (нет факта).
- Откат, берёт второй вариант: ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
унификация даёт ${\theta }_2=\{X/john,Y/sue\}$. Цели: [parent(john,Z), ancestor(Z,sue)].
- Проверяет parent(john,Z) — унифицируется с parent(john,mary), даёт $\{Z/mary\}$. Остаётся цель ancestor(mary,sue).
- Для ancestor(mary,sue) срабатывает база parent(mary,sue) — успех. Собирая подстановки, получаем доказательство ancestor(john,sue).
2) Какие вопросы могут привести к бесконечному поиску
- В самой данной программе (рекурсия стоит справа: parent(X,Z), ancestor(Z,Y)) при конечном множестве фактов обычно поиск конечен и выдаст все ответы (хотя может повторно пересчитывать одни и те же промежуточные результаты).
- Зацикливание возникает, если рекурсивный вызов стоит слева (леворекурсивное правило). Пример опасного правила:
ancestor(X,Y) :- ancestor(X,Z), parent(Z,Y).
Для запроса ?- ancestor(john,Y). резолюция делает левый рекурсивный вызов ancestor(john,...) снова и снова — без продвижения к факту parent(...), поэтому поиск зациклится (глубокая бесконечная рекурсия при DFS).
- Также возможны бесконечные попытки при полностью неограничённых переменных в сочетании с правилами, порождающими бесконечное ветвление, но главный практический источник — леворекурсивные определения при выборе стратегии поиска "глубина в первую очередь".
3) Как модифицировать программу для эффективного, безопасного поиска
- Сохранять рекурсивный вызов справа (как в вашем варианте). Это уже уменьшает риск бесконечного спуска при DFS.
- Таблирование (memoization / OLDT / tabling). В SWI-Prolog:
:- table ancestor/2.
Это сохраняет найденные пары ancestor/2 и устраняет повторные вычисления и многие типы зацикливаний, в том числе при леворекурсивных правилах (совет — лучший в большинстве случаев).
- Итеративное углубление (depth-limited search) — ограничивать глубину рекурсии и увеличивать лимит постепенно:
depth_anc( X, Y, 0 ) :- parent(X,Y).
depth_anc( X, Y, N ) :-
N>0,
parent(X,Z),
N1 is $N-1$,
depth_anc(Z,Y,N1).
ancestor_id(X,Y) :-
between(0,100,N),
depth_anc(X,Y,N).
(то есть сперва ищем пути длины $0$, потом $1$, и т.д.; убирает проблемы DFS с бесконечными ветвями)
- Использовать cut аккуратно, если нужен только первый (или единственный) ответ и вы хотите отсечь лишние ветви; но cut может скрыть нужные ответы, поэтому применять с осторожностью:
ancestor(X,Y) :- parent(X,Y), !.
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
(этот вариант даёт один способ для каждой пары — полезно для ускорения, но иногда нежелателен)
- Альтернатива — явно реализовать поиск с явной очередью (BFS) для поиска кратчайшего пути между предками; это требует дополнительного кода, но обеспечивает терминальность и кратчайшие решения.
Резюме: ваш вариант с рекурсией справа корректен и обычно не зацикливается при конечных фактах. Для повышения эффективности и гарантированной терминальности используйте таблирование (:- table ancestor/2) или итеративное углубление; избегайте леворекурсивных правил при использовании стандартного Prolog (DFS).