如果图 Graph 的某个节点 B 存在边 AB 或 BA,我遇到了这个 cut,它应该返回 true。
node(A,Graph) :- adjacent(A,_,Graph),!.
问题是我不明白为什么删除这个切口会对返回的解决方案产生任何影响。
据我了解,在 Prolog 语句末尾进行剪切的唯一用途是当有另一个同名的语句 [another node(...)] 如果第一个成功时我们不想被调用. 一个例子是一个函数,它接受 X 和 Y 并返回较大的一个作为第三个参数。
max1(X, Y, X) :- X > Y, !.
max1(_X, Y, Y).
但是,没有其他名为 node(...) 的语句,所以我看不到剪切如何影响解决方案。
这是我的代码。它应该找到一棵生成树。这里有详细解释。编译器是 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).
未删减返回的解决方案(正确)
?- 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.
使用 cut 返回的解决方案(不正确)
?- 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.