在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(X, Y) :- edge(Y, X).您的程序永远不会终止.无论您将此规则添加到程序中的哪个位置.经常令人恼火的是,你的程序仍会产生许多答案,这有点暗示它有效.但是,它永远不会停止.

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

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

edge(a, b) :- false.
edge(X, Y) :- edge(Y, X).

其次,在改进的程序中还有另一个不终止的来源.这是相关的故障片:

path(X, Y) :- false, edge1(X, Y).
path(X, Y) :- edge1(X, Z), path(Z, Y), false.

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).

Answer 2

因为规则与事实不同,如果你使用相同的谓词,你就会陷入无限循环.

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

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

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

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

......哦,哦.逻辑圈.

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