在Prolog中，为什么不添加“ Edge（X，Y）：-Edge（Y，X）”。单独工作以将有向图定义转换为无向图的工作

Question

我刚刚学习 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

Answer 1

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

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

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

好的， 当我们打电话时会发生什么 edge(2,5)?

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

...呃哦。逻辑圈。

使用时 edge1, ，您只需为谓词创建一个包装器来逃避递归定义。

Answer 2

您的程序中有几个潜在的不终止原因。

首先，有规律 edge(X, Y) :- edge(Y, X). 你的程序将 绝不 终止。无论您将此规则添加到程序的何处。通常令人恼火的是，您的程序仍然会产生许多答案，这在某种程度上表明它是有效的。然而，它永远不会停止。

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

path(X, Y) :- edge(X, Y), 错误的.
路径（X，Y）：- 错误的, 边(X, Z), 路径(Z, Y).

边缘（a，b）：- 错误的.
edge(X, Y) :- edge(Y, X).

其次，改进后的程序还有另一个不终止的原因。这是相关的故障切片：

路径（X，Y）：- 错误的, 边 1(X, Y).
path(X, Y) :- edge1(X, Z), path(Z, Y), 错误的.

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

edge(a, b).

edge1/2 现在总是包含循环，所以这个片段将循环 path(a, Y). 。更一般地说 path(X, Y), false.

为了解决这个问题，你必须重写 path/2.

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

所以 path/2 可以定义为：

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