Aufsammeln von Wegknoten in einer Akkumulatorliste
Verwendung einer Akkumulatorliste
Die Verwendung einer sogenannten Akkumulatorliste soll zunächst an einem einfachen Beispiel verdeutlicht werden.
% Akkumulatortest liste_verarbeiten([], A, A). liste_verarbeiten([K|R], A, V) :- print(K), liste_verarbeiten(R, [K|A], V).
Eine Anfrage zu dem liste_verarbeiten
-Prädikat könnte z.B. so aussehen.
?- liste_verarbeiten([1, 2, 3], [], L). 123 L = [3, 2, 1] ; No
Etwas mehr Klarheit verschafft die Auswertung der Anfrage im Trace-Modus.
?- trace. Yes [trace] ?- liste_verarbeiten([1, 2, 3], [], V). Call: (7) liste_verarbeiten([1, 2, 3], [], _G297) ? creep Call: (8) print(1) ? creep 1 Exit: (8) print(1) ? creep Call: (8) liste_verarbeiten([2, 3], [1], _G297) ? creep Call: (9) print(2) ? creep 2 Exit: (9) print(2) ? creep Call: (9) liste_verarbeiten([3], [2, 1], _G297) ? creep Call: (10) print(3) ? creep 3 Exit: (10) print(3) ? creep Call: (10) liste_verarbeiten([], [3, 2, 1], _G297) ? creep Exit: (10) liste_verarbeiten([], [3, 2, 1], [3, 2, 1]) ? creep Exit: (9) liste_verarbeiten([3], [2, 1], [3, 2, 1]) ? creep Exit: (8) liste_verarbeiten([2, 3], [1], [3, 2, 1]) ? creep Exit: (7) liste_verarbeiten([1, 2, 3], [], [3, 2, 1]) ? creep V = [3, 2, 1] ; Fail: (10) liste_verarbeiten([], [3, 2, 1], _G297) ? creep Fail: (9) liste_verarbeiten([3], [2, 1], _G297) ? creep Fail: (8) liste_verarbeiten([2, 3], [1], _G297) ? creep Fail: (7) liste_verarbeiten([1, 2, 3], [], _G297) ? creep No
Hieraus ergibt sich das folgende Herleitungsprotokoll.
?- liste_verarbeiten([1, 2, 3], [], L). benutze: liste_verarbeiten([K|R], A, V) :- print(K), liste_verarbeiten(R, [K|A], V). {K -> 1; R -> [2, 3]; A -> []; V -> L} ?- print(1), liste_verarbeiten([2, 3], [1], L). Ausgabe: 1 ?- liste_verarbeiten([2, 3], [1], L). benutze: liste_verarbeiten([K|R], A, V) :- print(K), liste_verarbeiten(R, [K|A], V). {K -> 2; R -> [3]; A -> [1]; V -> L} ?- print(2), liste_verarbeiten([3], [2, 1], L). Ausgabe: 2 ?- liste_verarbeiten([3], [2, 1], L). benutze: liste_verarbeiten([K|R], A, V) :- print(K), liste_verarbeiten(R, [K|A], V). {K -> 3; R -> []; A -> [3, 2, 1]; V -> L} ?- print(3), liste_verarbeiten([3], [2, 1], L). Ausgabe: 3 ?- liste_verarbeiten([], [3, 2, 1], L). benutze: liste_verarbeiten([], A, A). {A -> [3, 2, 1]; L -> [3, 2, 1]} L = [3, 2, 1] No
Man kann die Rolle der beiden Listen A und L so beschreiben: Die Akkumulatorliste A sammelt während der Auswertung der Anfrage alle verarbeiten Listenelemente auf. Wenn die zu verarbeitende Liste schließlich leer ist, wird die gesamte Akkumulatorliste an die Ausgabeliste L übergeben.
Die Regeln zur Festlegung des liste_verarbeiten
-Prädikats lassen sich demnach
so in Worten beschreiben:
Regel 1: liste_verarbeiten([], A, A). Die Verarbeitung der leeren Liste [] mit bereits verarbeitet Liste A ergibt die Liste A. Regel 2: liste_verarbeiten([K|R], A, V) :- print(K), liste_verarbeiten(R, [K|A], V). Die Verarbeitung der Liste [K|R] mit bereits verarbeiteter Liste A ergibt die Liste V, wenn K verarbeitet wird und wenn die Verarbeitung der Liste R mit bereits verarbeiteter Liste [K|A] die Liste V ergibt.
Aufgabe 1
Mit Hilfe einer Akkumulatorliste kann man auch die Wegsuche in einem Graphen realisieren.
% Graph kante(a, b). kante(a, c). kante(b, d). kante(b, e). kante(c, e). kante(c, f). kante(d, g). kante(d, e). kante(f, b). kante(f, i). kante(h, e). kante(h, b). kante(i, e). kante(i, h). % Weg weg1(X, X, W, W). weg1(X, Y, A, W) :- kante(X, Z), weg1(Z, Y, [Z|A], W). weg(X, Y, W) :- weg1(X, Y, [X], W).
(a) Teste zunächst das weg1
-(Hilfs-)Prädikat mit Anfragen der folgenden Art.
Deute die Ergebnisse.
?- weg1(a, b, [a], W). ...
(b) Beschreibe in Worten die "Logik" der beiden Regeln zum weg1
-Prädikat.