Definition des reflexiven transitiven Verschlusses

Viele Prädikate verwenden im Wesentlichen eine Form der transitiven Schließung, nur um zu entdecken, dass die Terminierung ebenfalls angesprochen werden muss. Warum lösen closure0/3 nicht immer und immer mit 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). 

Gibt es Fälle, in denen diese Definition nicht zur Umsetzung der transitiven Schließung verwendet werden kann?


Warum diff / 2?

Um @ WouterBeeks Kommentar im Detail zu beantworten: dif/2 oder iso_dif/2 sind ideal, weil sie potentielle Probleme iso_dif/2 oder signalisieren können. In aktuellen Implementierungen verbirgt die Schleife der obersten Ebene jedoch häufig die tatsächlichen Probleme. Betrachte das Ziel closure0(\_^_^true,a,b) was sicherlich an sich problematisch ist. Bei Verwendung der folgenden Systeme ist das eigentliche Problem direkt nicht sichtbar.

 | ?- closure0(\_^_^true,a,b). % SICStus yes ?- closure0(\_^_^true,a,b). % SWI true ; true ; true ... 

Beide Loops der obersten Ebene zeigen nicht, was wir eigentlich sehen wollen: die dangling constraints. In SICStus benötigen wir eine Pseudovariable, um eine Substitution zu erzeugen, in SWI muss die Abfrage mit call_residue_vars/2 umbrochen werden. Auf diese Weise werden nun alle Variablen angezeigt, an die Bedingungen geknüpft sind.

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

Es ist nützlich, aber meiner Meinung nach noch nicht ideal, weil ich keine doppelten Pfade zum Zeitpunkt ihrer Erstellung schneiden kann.

Betrachten Sie, mit dem vollständigen Graphen 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). 

Die folgende Abfrage hat jetzt eine superexponentielle Laufzeit, obwohl die Schließung tatsächlich in Polynomialzeit gefunden werden kann:

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

Es wäre großartig, wenn mit diesem Meta-Prädikat auch ein effizienterer Weg gefunden werden könnte, den Abschluss zu bestimmen.

Zum Beispiel würde man normalerweise den Algorithmus von Warshall verwenden, um den Verschluss in kubischer Zeit zu berechnen, mit einem Code ähnlich dem:

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

Nachgeben (mit allen Nachteilen im Vergleich zur schön deklarativen 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.