3

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

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。

我不明白，为什么它是递归的？

4

2 回答 2

2

的这个条款friends/2是有缺陷的：

friends(X,Y) :- friends(X,Z),friends(Y,Z).

把它翻译成英文：“如果X和Y有一个共同的朋友Z，那么X和Y就是朋友。”

或者，让我们专业化，X成为“我”，Y成为我的邻居“FooBert”，Z成为“你”：所以如果我是你的朋友，而 FooBert 是你的朋友……那会让我和 FooBert 成为朋友吗？我不这么认为，我讨厌那个人——他回家时总是砰的一声关上门。:)

我建议你考虑一下关系friends/2 应该具有的代数属性，它可能具有的那些，以及它不应该具有的那些。那么自反性、对称性、反对称性、传递性呢？

于 2015-04-28T20:42:05.650 回答
2

首先，两个假设：

  • 您要编写的实际代码如下所示，带有适当的点：

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

  • 传递性成立：朋友的朋友也是我的朋友（我宁愿将友谊建模为距离：“A 靠近 B”，“B 靠近 C”并不一定意味着“A 靠近 C”）。重复的答案是正确的，首先要弄清楚你想要建模什么。

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

一步步

那么，当我们问：friends(mia,X)？

  1. 第一个子句给出Y=ellen（您要求更多解决方案）
  2. 第二条给出Y=lucy（您再次要求更多解决方案）
  3. 堆栈溢出 ！

让我们详细说明第三个条款：

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

  2. 有这样的变量Z吗friends(mia,Z)？

    请注意，除了重命名 from Yto之外Z，我们问的问题与上面的步骤 1 相同吗？ 这闻起来像无限递归，但让我们看看......

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

这个问题类似于上下文无关文法中的无限左递归。

一个修复

有两个谓词：

  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会取得一点进展，即找到一个已知的朋友mia（无需递归），并且尝试（递归地）查找该朋友是否是其他人的朋友。

朋友的朋友

如果我们添加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，同时考虑上述属性。如果您想尝试，这应该不会太难实现。

于 2015-04-28T21:28:50.990 回答