在 Prolog 语句的末尾剪切

Question

我遇到过这种切割，如果图 Graph 的某个节点 B 存在边 A-B 或 B-A，它应该 return 为真。

node(A,Graph) :- adjacent(A,_,Graph),!.

问题是我不明白为什么删除这个削减会对 returned 解决方案产生任何影响。

据我所知，Prolog 语句的 cut at the end 的唯一用途是存在另一个我们不想成为的同名语句 [another node(...)]如果第一个成功则调用。一个例子是将 X 和 Y 和 returns 作为第三个参数的函数。

max1(X, Y, X) :- X > Y, !.
max1(_X, Y, Y).

但是，没有其他名为 node(...) 的语句，所以我看不出切割会如何影响解决方案。

这是我的代码。它应该找到一个生成树。详细解释here。编译器是 linux.

上的 SWI-Prolog 7.6.4

:- op(900, fy, not).

stree1( Graph, Tree)  :-
    subset( Graph, Tree),  tree( Tree),  covers( Tree, Graph).

tree( Tree)  :-
    connected( Tree),  not hasacycle( Tree).

connected( Graph)  :-
    not ( node( A, Graph), node( B, Graph), not path( A, B, Graph, _) ).

hasacycle( Graph)  :-
     adjacent( Node1, Node2, Graph),
     path( Node1, Node2, Graph, [Node1, X, Y | _] ). 

covers( Tree, Graph)  :-
    not ( node( Node, Graph), not node( Node, Tree) ).

subset( [], [] ). 
subset( [X | Set], Subset)  :-  subset( Set, Subset).
subset( [X | Set], [X | Subset])  :-  subset( Set, Subset).

adjacent( Node1, Node2, Graph)  :-
      member( Node1-Node2, Graph)
      ;
      member( Node2-Node1, Graph).

node( Node, Graph)  :-  adjacent( Node, _, Graph). 

path( A, Z, Graph, Path)  :-
      path1( A, [Z], Graph, Path).

path1( A, [A | Path1], _, [A | Path1] ).

path1( A, [Y | Path1], Graph, Path)  :-
      adjacent( X, Y, Graph),
      not member( X, Path1), 
      path1( A, [X, Y | Path1], Graph, Path).

解决方案return未经删减（正确）

?- stree1([a-b, b-c, b-d, c-d], Tree).
Tree = [a-b, b-d, c-d] ;
Tree = [a-b, b-c, c-d] ;
Tree = [a-b, b-c, b-d] ;
false.

解决方案return剪辑（不正确）

?- stree1([a-b, b-c, b-d, c-d], Tree).
Tree = [a-b] ;
Tree = [a-b, c-d] ;
Tree = [a-b, b-d] ;
Tree = [a-b, b-d, c-d] ;
Tree = [a-b, b-c] ;
Tree = [a-b, b-c, c-d] ;
Tree = [a-b, b-c, b-d] ;
false.

Answer 1

"As I understand it the only use for a cut at the end of a Prolog statement is when there is another statement with the same name [another node(...)] which we don't want to be called if the first one succeedes."

好吧，这对你的情况来说是不正确的，因为你使用的是 member/2 谓词，它可以与回溯一起使用。在这种情况下，使用切割将 p运行e Prolog 在回溯中使用的解决方案树，并可能导致您获得的结果发生变化。为了举例说明，请在此处查看原始 post 的略微修改代码：

node( Node, Graph , Target)  :-  adjacent( Node, Target, Graph),!.

adjacent( Node1, Node2, Graph)  :-
  member( Node1-Node2, Graph)
  ;
  member( Node2-Node1, Graph).

当您在控制台中运行此查询时，您将看到输出：

?- node(l,[l-x,l-y],Target).
Target = x

为什么？因为一开始，你的搜索树有两片叶子。对 (l-x) 或 (l-y) 满足 adjacent/3 中的条件。然后，根据深度优先搜索，选择 (l-x) 对，并且由于代码中有 ! 语句，搜索树的其余部分现在是 p运行ed。因此，您得到的结果为 Target = x

但是，如果您从代码中删除 ! 语句，您将看到：

?- node(l,[l-x,l-y],Target).
Target = x ;
Target = y ;
false.

在这里，您会看到搜索树的两个叶子都按照深度优先的顺序依次执行，并且您会看到两个结果。这就是导致您在 ! 存在与否时看到不同结果的原因。

在 Prolog 语句的末尾剪切

Cut at the end of a Prolog statement

prolog

spanning-tree

prolog-cut