首頁猿問自反傳遞閉包的定義

自反傳遞閉包的定義

源碼算法與數(shù)據(jù)結(jié)構(gòu)

小唯快跑啊 2019-07-02 11:26:39

自反傳遞閉包的定義許多謂詞本質(zhì)上使用某種形式的傳遞閉包，結(jié)果發(fā)現(xiàn)終止也必須解決。為什么不一勞永逸地用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).是否有這種定義不能用于實(shí)現(xiàn)傳遞閉包的情況？為什么是dif/2？要詳細(xì)回答@WouterBeek的評(píng)論：dif/2或iso_dif/2是理想的，因?yàn)樗麄兡軌蝻@示或暗示潛在的問題。然而，在當(dāng)前的實(shí)現(xiàn)中，頂層循環(huán)常常隱藏實(shí)際問題?？紤]一下目標(biāo)closure0(\_^_^true,a,b)這本身就有相當(dāng)大的問題。當(dāng)使用以下系統(tǒng)時(shí)，實(shí)際問題直接不可見。| ?- closure0(\_^_^true,a,b). % SICStus yes ?- closure0(\_^_^true,a,b). % SWI true ; true ; true ...兩個(gè)頂級(jí)循環(huán)都沒有顯示我們真正想看到的東西：懸空約束。在SICStus中，我們需要一個(gè)偽變量來產(chǎn)生某種替換，在SWI中，查詢必須用call_residue_vars/2..現(xiàn)在以這種方式顯示所有附加約束的變量。| ?- 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貢獻(xiàn)1836條經(jīng)驗(yàn) 獲得超13個(gè)贊

這是有用的，但在我看來還不是理想的，因?yàn)槲也荒芮懈钪貜?fù)的路徑，在他們的創(chuàng)造點(diǎn)。

考慮一下，用完全圖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).

下面的查詢現(xiàn)在具有超級(jí)指數(shù)運(yùn)行時(shí)，盡管閉包實(shí)際上可以在多項(xiàng)式時(shí)間內(nèi)找到：

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

如果確定閉包的更有效的方法也可以用這個(gè)元謂詞來表達(dá)，那就太好了。

例如，人們通常只需使用Warwhar的算法以立方時(shí)間計(jì)算閉包，代碼類似于：

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

屈服(與良好的聲明性相比有所有缺點(diǎn))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.

反對(duì) 回復(fù) 2019-07-02