prolog - 序言中的递归引用

Question

我在尝试实现时遇到了一些问题

friends(mia, ellen).
friends(mia, lucy).
friends(X,Y) :-
  friends(X,Z),
  friends(Y,Z).

当我询问 ?- friends(mia, X). 时，它用完了本地堆栈。

然后我添加

friends(ellen, mia) friends(lucy, mia) 

我问 ?- friends(mia, X). ，它一直回复 X = mia。

没看懂，为什么要递归？

Answer 1

首先，两个假设:

• 您想要编写的实际代码如下，带有适当的点:

  friends(mia,ellen).
  friends(mia,lucy).
  friends(X,Y) :- 
     friends(X,Z),
     friends(Z,Y).
  

• 传递性成立: friend 的 friend 也是我的 friend (我宁愿将友谊建模为距离:“A 靠近 B”和“B 靠近 C”并不一定意味着“A 靠近 C”) . repeat's answer首先弄清楚你想要建模什么是正确的。

现在，让我们看看为什么要进入无限递归。

循序渐进

那么，当我们问:friends(mia,X) 时会发生什么？ ？

1. 第一个子句给出 Y=ellen (你要求更多的解决方案)
2. 第二个子句给出 Y=lucy (你再次要求更多的解决方案)
3. 堆栈溢出!

让我们详细说明第三个子句:

1. 我想知道是否 friends(mia,Y)对某些变量成立 Y .

2. 有没有变量Z这样 friends(mia,Z)持有？

   请注意，除了从 Y 重命名之外至 Z ，我们问的是与上面第 1 步相同的问题？ 这听起来像是无限递归，但让我们看看...

3. 我们尝试 friends 的前两个子句, 但后来我们失败了，因为没有 friends(ellen,Y)也不friends(lucy,Y) , 所以...
4. 我们调用第三个子句以查找是否存在可传递的友谊，并且我们返回到步骤 1 没有任何进一步的进展 => 无限递归。

这个问题类似于无限Left recursion在上下文无关文法中。

修复

有两个谓词:

1. known_friends/2 , 这给出了直接关系。

2. friends/2 ，它也编码传递性

   known_friends(mia,ellen).
   known_friends(mia,lucy).
   
   friends(X,Y) :- known_friends(X,Y).
   friends(X,Y) :- known_friends(X,Z), friends(Z,Y).
   

现在，当我们询问 friends(mia,X) , friends/2给出与 known_friends/2 的两个子句相同的答案, 但没有找到传递子句的任何答案:这里的区别是 known_friends会有一点进步，就是找一个认识的 friend mia (没有递归)，并尝试(递归)查找该 friend 是否是其他人的 friend 。

friend 的 friend

如果我们添加 known_friends(ellen, bishop) ^:-) 然后 friends还会找到 Y=bishop ，因为:

• known_friends(mia,ellen)持有，并且
• friends(ellen,bishop)递归地找到。

圆度

如果您在友谊图中添加循环依赖项(在 known_friends 中)，那么您将使用 friends 无限遍历此图.在解决该问题之前，您必须考虑以下问题:

• 是否friends(X,Y) <=> friends(Y,X)为所有人保留(X,Y) ？
• 那friends(X,X)呢？ , 对于所有 X ？

然后，你应该在评估friends时保留一组所有见过的人。为了检测您何时循环遍历 known_friends ，同时考虑到上述属性。如果您想尝试，这应该不会太难实现。