Вопрос #1614932
Проанализируйте Prolog-фрагмент: parent(john,mary). parent(mary,sue). ancestor(X,Y):- parent(X,Y). ancestor(X,Y):- parent(X,Z), ancestor(Z,Y). — что возвращает запрос ancestor(john,Y) и как добавить правило для избегания бесконечной рекурсии
- \(Y = mary\) (по факту \(\texttt{parent(john,mary).}\)),
- затем \(Y = sue\) (по \(\texttt{parent(john,mary)}\) и рекурсивно \(\texttt{parent(mary,sue)}\)),
- затем нет других решений (false).
Чтобы избежать бесконечной рекурсии при наличии циклов в графе родства, используйте проверку посещённых вершин (аккумулятор visited). Пример:
\[
\begin{aligned}
\texttt{ancestor(X,Y)} &:- \texttt{ancestor(X,Y,[X]).}\\
\texttt{ancestor(X,Y,\_)} &:- \texttt{parent(X,Y).}\\
\texttt{ancestor(X,Y,Visited)} &:- \texttt{parent(X,Z)},\ \texttt{\+ member(Z,Visited)},\ \texttt{ancestor(Z,Y,[Z|Visited]).}
\end{aligned}
\]
Если нет встроенной \(\texttt{member/2}\), добавьте:
\[
\begin{aligned}
\texttt{member(X,[X|\_]).}\\
\texttt{member(X,[\_|T])} &:- \texttt{member(X,T).}
\end{aligned}
\]
Альтернатива: в Prolog с таблированием (tabling) — \(\texttt{:- table ancestor/2.}\) — тоже предотвращает бесконечные циклы.