 |
|||
| HSG |
|
Breitensuche verfolgt von Anfang an alle möglichen Wege. Man findet also automatisch einen minimalen Weg zuerst.
Prolog-Programm (nach Informatik mit Prolog, Gerhard Röhner, S.63)
kante(a,b).
kante(a,c).
kante(b,d).
kante(b,e).
kante(c,e).
kante(c,f).
kante(d,g).
kante(e,f).
kante(e,g).
kante(e,h).
kante(f,i).
kante(g,h).
kante(g,j).
kante(h,i).
kante(h,k).
kante(i,m).
kante(j,k).
kante(k,m).
verbunden(A,B):- kante(A,B).
verbunden(A,B):- kante(B,A).
breitensuche(Start,Ziel,Loesung):-breitensuche([Start],[],Ziel,Loesung).
breitensuche(Pfad,Pfade,Ziel,Loesung):-Pfad=[Ziel|_],Pfad=Loesung,!.
breitensuche(Pfad,Pfade,Ziel,Loesung):-Pfad=[KnotenA|_],
findall([KnotenN|Pfad],
(verbunden(KnotenA,KnotenN),not(member(KnotenN,Pfad))),
GefundenePfade),
append(Pfade,GefundenePfade,NeuePfade),
NeuePfade=[PfadN|RestPfade],
breitensuche(PfadN,RestPfade,Ziel,Loesung).
Erläuterungen zu breitensuche(Pfad,Pfade,Ziel,Loesung):
- Zunächst wird überprüft, ob der Kopf (der Pfad wird umgedreht aufgebaut) des aktuellen Pfades der Zielknoten ist. Ist das der Fall, so wird der Pfad als Lösung ausgegeben und mit einem Cut die Suche nach weiteren Lösungen abgebrochen.
- Im Rekursionsfall wird zunächst der aktuelle KnotenA dem aktuellen Pfad entnommen.
- Mit findall werden alle Verbindungen zu neuen KnotenN gesucht, die nicht im bisherigen Pfad (Zyklen vermeiden!) enthalten sind. In die Lösungsliste werden aber jeweils komplette Pfade (bisheriger Pfad ergänzt um den KnotenN) eingetragen.
- Die eben gefundenen Pfade werden an die Liste der übergebenen Pfade angehängt.
- Die gerade entstandene Liste der Pfade wird in den Kopf PfadN und den Rest RestPfade aufgetrennt.
- breitensuche wird rekursiv aufgerufen mit PfadN als aktuellem Pfad und RestPfade als Pfadliste. Es wird also gewissermaßen der Kopf der Liste Pfade abgetrennt und bearbeitet.
Arbeitsweise des Algorithmus am Beispiel breitensuche(e,i,L)
