 |
|||
| HSG |
|
Tiefensuche (depth first search, dfs)
Tiefensuche versucht durch stetiges Erweitern eines Weges zum Ziel zu gelangen. Im Misserfolgsfall werden durch Backtracking andere Verzweigungen gewählt.
Algorithmus 1 zur Wegsuche von X nach Y mit Vermeidung von Zyklen (nach Informatik mit Prolog, Gerhard Röhner, S.61)
pfeil(a,b).
pfeil(a,c).
pfeil(a,d).
pfeil(b,c).
pfeil(c,d).
pfeil(c,e).
pfeil(d,e).
pfeil(c,a).
weg(X,Y):-pfeil(X,_),pfeil(_,Y),tiefensuche(X,Y,Loesung).
tiefensuche(Start,Ziel,Loesung):-tiefensuche(Start,[Start],Ziel,Loesung).
tiefensuche(Ziel,Pfad,Ziel,Loesung):-Loesung = Pfad,!.
tiefensuche(KnotenA,Pfad,Ziel,Loesung):-pfeil(KnotenA,KnotenN),
not(member(KnotenN,Pfad)),
tiefensuche(KnotenN,[KnotenN|Pfad],Ziel,Loesung).
In "tiefensuche(Ziel,Pfad,Ziel,Loesung):-Loesung = Pfad,!." wird ein Cut verwendet und es kommt die 'Akkumulatortechnik' zur Anwendung.
Tiefensuche kann im Einzelfall sehr ungünstig verlaufen.
Algorithmus 2 zur Wegsuche von X nach Y mit Vermeidung von Zyklen (nach Grundkurs Informatik, H.-U. Zimmermann, S.65)
- Zuerst wird geprüft, ob es Kanten von X weg und zu Y hin gibt. Nur so kann es einen Weg von X zu Y geben.
- Alle von X aus direkt erreichbaren Knoten werden in eine Nachfolger-Liste gespeichert.
- Die Weg-Liste wird mit [X] gestartet.
- Als Nachfolge-Knoten Z wird das erste Element der Nachfolger-Liste entnommen und der Weg-Liste hinzugefügt.
- Die Nachfolger-Liste wird vorne (Tiefensuche!) um mögliche Nachfolger ergänzt.
- In der Nachfolger-Liste werden schon besuchte Knoten gestrichen.
- Die Schritte 4 bis 6 werden solange wiederholt bis das Ziel Y erreicht ist oder die Nachfolger-Liste leer ist.
Umsetzung in Prolog
pfeil(a,b).
pfeil(a,c).
pfeil(a,d).
pfeil(b,c).
pfeil(c,d).
pfeil(c,e).
pfeil(d,e).
pfeil(c,a).
weg(X,Y):-pfeil(X,_),pfeil(_,Y),weg1(X,Y,[],[]).
weg1(Start,Ziel,Anwaerter,Besucht):-Start=Ziel,
append(Besucht,[Ziel],Route),write(Route).
weg1(Start,Ziel,Anwaerter,Besucht):-append(Besucht,[Start],BesuchtNeu),
findall(N,pfeil(Start,N),Nachfolger),
append(Nachfolger,Anwaerter,AnwaerterNeu),
subtract(AnwaerterNeu,BesuchtNeu,[K|R]),
weg1(K,Ziel,[K|R],BesuchtNeu).
'Schachteldiagramm' zu weg1(a,e,[ ],[ ]).
Verwendete Systemprädikate:
append (append(L1,L2,L3) fügt die Listen L1 und L2 zu L3 zusammen),
findall ( findall(X,p(X),L) sammelt in der Liste L alle X, die p(X) wahr machen) ,
subtract ( subtract(A,B,D) ermittelt die Differenzmenge D = A\B )
Detail
Der Abbruch bei leerer Anwärterliste geschieht in subtract(AnwaerterNeu,BesuchtNeu,[K|R]) , weil [ ] = [K|R] fehlschlägt.
Vergleich der Algorithmen 1 und 2
Algorithmus 2 findet höchstens eine Lösung und ist aufwändiger, Algorithmus 1 findet alle Lösungen und ist kürzer.
Anwendung
| In der Aufgabe 21 auf Seite 26 von G.Röhner, Informatik mit Prolog soll ein Weg von a nach g gesucht werden. Herr Röhner schlägt vor, das Labyrinth durch die vorhandenen Türen zu beschreiben. Da man eine Tür in beiden Richtungen beschreiten kann, lässt sich mit pfeil(X,Y):-tuer(X,Y). und pfeil(Y,X):-tuer(X,Y). eine Anpassung an obige Notation vornehmen. |
|
tuer(a,b).
tuer(b,e).
tuer(b,c).
tuer(d,e).
tuer(c,d).
tuer(e,f).
tuer(g,e).
pfeil(X,Y):-tuer(X,Y).
pfeil(X,Y):-tuer(Y,X).
tiefensuche(Start,Ziel,Loesung):-pfeil(Start,_),pfeil(_,Ziel),
tiefensuche(Start,[Start],Ziel,Loesung).
tiefensuche(Ziel,Pfad,Ziel,Loesung):-Loesung = Pfad,!.
tiefensuche(KnotenA,Pfad,Ziel,Loesung):-pfeil(KnotenA,KnotenN),
not(member(KnotenN,Pfad)),
append(Pfad,[KnotenN],PfadNeu),
tiefensuche(KnotenN,PfadNeu,Ziel,Loesung).
Obiges Programm verwendet eine leicht modifizierte Tiefensuche: Neue Knoten werden mit append hinten an den Pfad angehängt. So wird der Pfad am Schluss in der richtigen Orientierung ausgegeben.
?- tiefensuche(a,g,L). L = [a, b, e, g] ; L = [a, b, c, d, e, g] ;
