自反传递闭包的定义
许多谓词本质上使用某种形式的传递闭包，只是发现终止也必须被解决。 为什么不用closure0/3解决这个问题closure0/3 ：
:- meta_predicate closure0(2,?,?). :- meta_predicate closure(2,?,?). :- meta_predicate closure0(2,?,?,+). % internal closure0(R_2, X0,X) :- closure0(R_2, X0,X, [X0]). closure(R_2, X0,X) :- call(R_2, X0,X1), closure0(R_2, X1,X, [X1,X0]). closure0(_R_2, X,X, _). closure0(R_2, X0,X, Xs) :- call(R_2, X0,X1), non_member(X1, Xs), closure0(R_2, X1,X, [X1|Xs]). non_member(_E, []). non_member(E, [X|Xs]) :- dif(E,X), non_member(E, Xs).
有没有这个定义不能用于实现传递闭包的情况？
为什么dif / 2？
要详细回答@ WouterBeek的评论： dif/2或者iso_dif/2是理想的，因为他们能够显示或者发出潜在的问题。 但是，在当前的实现中，顶级循环往往隐藏了实际的问题。 考虑目标closure0(\_^_^true,a,b)本身肯定是相当有问题的。 当使用以下系统时，实际的问题是不可见的。
| ?- closure0(\_^_^true,a,b). % SICStus yes ?- closure0(\_^_^true,a,b). % SWI true ; true ; true ...
这两个顶级循环都不显示我们真正想看到的：悬挂约束。 在SICStus中，我们需要一个伪变量来产生一些替换，在SWI中，查询必须用call_residue_vars/2进行包装。 以这种方式，现在显示所有有附加限制的变量。
| ?- closure0(\_^_^true,a,b), Alt=t. % SICStus Alt = t ? ; Alt = t, prolog:dif(_A,a), prolog:dif(b,_A) ? ; Alt = t, prolog:dif(_A,a), prolog:dif(_B,_A), prolog:dif(_B,a), prolog:dif(b,_B), prolog:dif(b,_A) ... ?- call_residue_vars(closure0(\_^_^true,a,b),Vs). % SWI Vs = [] ; Vs = [_G1744, _G1747, _G1750], dif(_G1744, a), dif(b, _G1744) ; Vs = [_G1915, _G1918, _G1921, _G1924, _G1927, _G1930, _G1933], dif(_G1915, a), dif(b, _G1915), dif(_G1921, _G1915), dif(_G1921, a), dif(b, _G1921) ...
这是有用的，但在我看来，还不是理想的，因为我不能在他们创造的时候减少重复的路径。
考虑完整的图K_n ：
n_complete(N, Es) :- numlist(1, N, Ns), phrase(pairs(Ns), Es). adjacent(Edges, X, Y) :- member(edge(X, Y), Edges). pairs([]) --> []. pairs([N|Ns]) --> edges(Ns, N), pairs(Ns). edges([], _) --> []. edges([N|Ns], X) --> [edge(X,N),edge(N,X)], edges(Ns, X).
以下查询现在具有超指数运行时，尽管实际上可以在多项式时间中找到闭包：
?- length(_, N), n_complete(N, Es), portray_clause(N), time(findall(Y, closure0(adjacent(Es), 1, Y), Ys)), false. 1. 16 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 1982161 Lips) 2. 54 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4548901 Lips) 3. 259 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 14499244 Lips) 4. 1,479 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 16219595 Lips) 5. 9,599 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 27691393 Lips) 6. 70,465 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 28911161 Lips) 7. 581,283 inferences, 0.020 CPU in 0.020 seconds (100% CPU, 29397339 Lips) 8. 5,343,059 inferences, 0.181 CPU in 0.181 seconds (100% CPU, 29488001 Lips) 9. 54,252,559 inferences, 1.809 CPU in 1.808 seconds (100% CPU, 29994536 Lips) 10. 603,682,989 inferences, 19.870 CPU in 19.865 seconds (100% CPU, 30381451 Lips)
如果能够用这个元谓语来表达一个更有效的方法来确定闭包，那将是非常好的。
例如，通常只需使用Warshall的算法来计算立方时间的闭包，其代码类似于：
node_edges_closure(Node, Edges, Closure) :- warshall_fixpoint(Edges, [Node], Closure). warshall_fixpoint(Edges, Nodes0, Closure) :- findall(Y, (member(X, Nodes0), adjacent(Edges, X, Y)), Nodes1, Nodes0), sort(Nodes1, Nodes), ( Nodes == Nodes0 -> Closure = Nodes0 ; warshall_fixpoint(Edges, Nodes, Closure) ).
屈服（相对于很好的声明性closure0/3 ，所有缺点）：
?- length(_, N), n_complete(N, Es), portray_clause(N), time(node_edges_closure(1, Es, Ys)), false. 1. % 16 inferences, 0.000 CPU in 0.000 seconds (75% CPU, 533333 Lips) 2. % 43 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1228571 Lips) 3. % 69 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1769231 Lips) 4. % 115 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 2346939 Lips) 5. % 187 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 2968254 Lips) 6. % 291 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 3548780 Lips) 7. % 433 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 3866071 Lips) 8. % 619 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 4268966 Lips) 9. % 855 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 4500000 Lips) 10. % 1,147 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4720165 Lips) etc.
