6

我只是在学习 Prolog，我正在复习讲义，所有的笔记都说：

给定有向图的以下定义：

path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

如果我们想让它成为一个无向图， edge(X, Y) :- edge(Y, X).单独定义是行不通的，我不知道为什么。如果 Y 到 X 有边，则 X 到 Y 有边。对我来说似乎很有意义。

注释并没有真正说明为什么不这样做，但它确实定义了正确的解决方案是：

edge1(X, Y) :- edge(X, Y).
edge1(X, Y) :- edge(Y, X).

到我们已经拥有的。

谁能给我解释一下，谢谢？<3

4

2 回答 2

7

您的程序中有几个潜在的未终止来源。

首先，根据规则，edge(X, Y) :- edge(Y, X).您的程序将永远不会终止。无论您将此规则添加到程序的哪个位置。通常很烦人的是，您的程序仍然会产生许多答案，这在某种程度上表明它有效。然而，它永远不会停止。

理解这一点的最好方法是考虑一个稍微修改过的程序，称为failure-slice。这个修改后的程序将与您的程序共享许多属性。不是全部，而是一些。我们会将目标添加false到您的计划中。如果生成的程序循环，原始程序也会循环。

路径（X，Y）：- 边缘（X，Y），假。
路径（X，Y）：-假，边缘（X，Z），路径（Z，Y）。

边缘（a，b）：-假。
边缘（X，Y）：-边缘（Y，X）。

其次，在您改进的程序中还有另一个不终止的来源。这是相关的故障片：

path(X, Y) :- false , edge1(X, Y)。
路径（X，Y）：- edge1（X，Z），路径（Z，Y），假。

边缘1（X，Y）：-边缘（X，Y）。
边缘1（X，Y）：-边缘（Y，X）。

边（a，b）。

edge1/2现在总是包含循环，所以这个片段将循环为path(a, Y). 并且更普遍地也是path(X, Y), false。

要解决这个问题，您将不得不重写path/2.

closure0/3您可以使用and以通用方式重写它path/4！

所以path/2可以定义为：

path(X, Y) :-
   closure(edge, X, Y).
于 2014-04-14T09:49:37.870 回答
6

因为规则与事实的工作方式不同，如果使用相同的谓词，您将陷入无限循环。

让我们举个例子?-edge(5,2)。我们最终会打电话给——

edge(5,2) :- edge(2,5).

好的，当我们调用时会发生什么 edge(2,5)？

edge(2,5) :- edge(5,2).

……呃哦。逻辑圈。

使用 时edge1，您只需为谓词创建一个包装器以转义递归定义。

于 2014-04-14T04:15:43.557 回答