 |
|||
| HSG |
|
Ungünstiger Verlauf der Tiefensuche
Im folgenden Prolog-Programm wurde im Beispiel aus Röhner, Informatik mit Prolog, S.61 - heimtückisch - die Reihenfolge der Knoten in zwei Kanten getauscht. Die Anfrage ?- tiefensuche(e,i,L) führt dann zu einer ausgedehnten Wanderung:
/* ?- tiefensuche(e,i,L). verläuft ungünstig */
kante(a,b,2).
kante(a,c,3).
kante(b,d,6).
kante(b,e,3).
kante(c,e,1).
kante(c,f,2).
kante(d,g,1).
kante(e,f,2).
kante(e,g,1).
kante(e,h,7).
kante(i,f,9). % vertauscht
kante(g,h,2).
kante(g,j,9).
kante(i,h,2). % vertauscht
kante(h,k,8).
kante(i,m,2).
kante(j,k,3).
kante(k,m,1).
verbunden(A,B):- kante(A,B,_).
verbunden(A,B):- kante(B,A,_).
tiefensuche(Start,Ziel,Loesung):-tiefensuche(Start,[Start],Ziel,Loesung).
tiefensuche(Ziel,Pfad,Ziel,Loesung):-Loesung = Pfad,!.
tiefensuche(KnotenA,Pfad,Ziel,Loesung):-
verbunden(KnotenA,KnotenN),not(member(KnotenN,Pfad)),
tiefensuche(KnotenN,[KnotenN|Pfad],Ziel,Loesung).
