Коротко о программе
- Факты: $\text{parent}(john,mary).$ и $\text{parent}(mary,anne).$ - Правила (в Prolog): $\text{ancestor}(X,Y):-\text{parent}(X,Y).$ и $\text{ancestor}(X,Y):-\text{parent}(X,Z),\text{ancestor}(Z,Y).$
Как Prolog ищет решения (SLD-разрешение, поиск в глубину слева направо)
1. Пример запроса $\text{?- ancestor}(john,anne).$ - Prolog пытается применить первое правило: проверить $\text{parent}(john,anne)$ — неудача.
- Пробует второе правило: сопоставляет голову $\text{ancestor}(X,Y)$ с $\text{ancestor}(john,anne)$, получая подстановку $X=john,Y=anne$. Поставленная цель становится $\text{parent}(john,Z),\text{ancestor}(Z,anne)$.
- Проверяет левую цель $\text{parent}(john,Z)$: находит факт $\text{parent}(john,mary)$ → подстановка $Z=mary$.
- Теперь остаётся цель $\text{ancestor}(mary,anne)$. Проверяет первое правило: $\text{parent}(mary,anne)$ есть факт → успех.
- Итог: найдено решение с $X=john,Y=anne$.
2. Пример запроса $\text{?- ancestor}(X,anne).$ - Сначала найдётся $\text{parent}(X,anne)$ — да: $X=mary$ (прямой предок).
- При запросе следующего решения Prolog вернётся к рекурсивному правилу и найдёт «mary» как промежуточную вершину для $X=john$. Порядок выдачи будет: $X=mary$, потом $X=john$.
Ключевые особенности поиска
- Поиск — глубинный (depth-first) и слева направо; при неудаче происходит откат (backtracking).
- Унификация сопоставляет переменные с конкретными термами; найденные подстановки распространяются на последующие цели (прямое применение примера: $Z=mary$).
Проблемы при больших базах и сложности
- Возможна зацикленность/непрекращение: при наличии циклов в графе фактов (например, если есть замкнутые родственные связи) и неудачном порядке целей Prolog может войти в бесконечную рекурсию.
- Повторные вычисления: рекурсивные запросы без запоминания промежуточных результатов приводят к многократному пересчитыванию одних и тех же подцелей — экспоненциальный рост в худшем случае, примерно $\mathcal{O}(b^d)$, где $b$ — среднее число ответвлений (число подходящих фактов/правил), $d$ — глубина рекурсии.
- Поиск по большому набору фактов замедляется, если нет индексации по аргументам предиката — Prolog вынужден перебирать много альтернатив.
- Память и стек: глубокая рекурсия может переполнить стек (stack overflow).
Как улучшить работу на больших данных
- Индексация предикатов: уменьшает число проверяемых фактов.
- Таблирование (memoization, SLG/трейлинг) — например, XSB или таблирование в SWI-Prolog: запоминает ответы подцелей и избегает повторных вычислений и многих зацикливаний.
- Использовать алгоритмы на уровне графа (для отношения предка — транзитивное замыкание): BFS/DFS со стандартной временной сложностью $\mathcal{O}(|V|+|E|)$ для одного источника, что часто эффективнее «сырых» рекурсий.
- Переписать правила/порядок целей, чтобы рекурсивный вызов был последним (хвостовая рекурсия) или переставить цели, чтобы сначала сужать пространство поиска.
- Использовать ограничения, отсечение (!), или лимиты глубины/итеративное углубление при необходимости.
Итого: на маленьких наборах пример работает просто и предсказуемо (находит mary, john и т.д.), но на больших — нужно внимание к порядку целей, индексации, таблированию и применению специализированных алгоритмов, иначе возможна неэффективность или бесконечные вычисления.