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.