自反傳遞閉包的定義許多謂詞本質上使用某種形式的傳遞閉包，結果發現終止也必須解決。為什么不一勞永逸地用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) ...
1 回答
開心每一天1111
TA貢獻1836條經驗 獲得超13個贊
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)
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.
添加回答
舉報
0/150
提交
取消