 |
|||
| HSG |
|
Die heuristische Suche entsteht aus der Breitensuche, in dem jedem noch zu untersuchenden
Pfad eine Bewertung zugeordnet wird und die Liste der zu untersuchenden Pfade entsprechend der
Bewertung geordnet ist. Diese Bewertung kann z.B. aus den Kosten entstehen, die ein Durchlauf
des Pfades verursacht.
Der Pfad [f,e,b,a] von a nach f hat z.B. eine Bewertung von 2+3+2=7. Im folgendem Prolog-Programm wird das mit pfad([f,e,b,a],7) modelliert.
Kommt zu einem Pfad, der in KnotenA endet, ein neuer KnotenN hinzu, so erweitert sich nicht nur der Pfad, sondern auch die Kosten. Im folgenden Prolog-Programm erledigen die Prädikate bewerte_heuristisch(+KnotenA,+KostenA,+KnotenN,-KostenN) und kostet(+A,+B,-Kosten) diese Aufgabe.
Die im Laufe der heuristischen Suche gefundenen neuen Pfade müssen in die Pfade-Liste einsortiert werden. Das erledigt in folgendem Programm das Prädikat sortiere_gefPfade_ein(+GefundenePfade,+PfadeAlt,-PfadeNeu).
sortiere_gefPfade_ein greift dabei auf das Prädikat sortiere_Pfad_ein(+Pfad,+ListeAlt,-ListeNeu) zurück.
Prolog-Programm (nach Informatik mit Prolog, Gerhard Röhner, S.63)
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(f,i,9).
kante(g,h,2).
kante(g,j,9).
kante(h,i,2).
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,_).
kostet(A,B,Kosten):-kante(A,B,Kosten).
kostet(A,B,Kosten):-kante(B,A,Kosten).
bewerte_heuristisch(KnotenA,KostenA,KnotenN,KostenN):-
kostet(KnotenA,KnotenN,KantenKosten),
KostenN is KostenA+KantenKosten.
sortiere_gefPfade_ein([],Liste,Liste).
sortiere_gefPfade_ein([K|R],Liste1,Liste3):-
sortiere_Pfad_ein(K,Liste1,Liste2),
sortiere_gefPfade_ein(R,Liste2,Liste3).
sortiere_Pfad_ein(Pfad,[],[Pfad]).
% Pfade mit kleineren Kosten stehen weiter vorne
sortiere_Pfad_ein(Pfad1,[Pfad2|Rest],[Pfad1,Pfad2|Rest]):-
Pfad1=pfad(_,K1),Pfad2=pfad(_,K2),K1=<K2,!.
% hierher kommt man wegen des Cuts nur im Fall K1>K2
sortiere_Pfad_ein(Pfad1,[Pfad2|Rest1],[Pfad2|Rest2]):-
sortiere_Pfad_ein(Pfad1,Rest1,Rest2).
heuristischeSuche(Start,Ziel,Loesung):-
heuristischeSuche(pfad([Start],0),[],Ziel,Loesung).
heuristischeSuche(Pfad,Pfade,Ziel,Loesung):-Pfad=pfad([Ziel|_],_),
Pfad=Loesung,!.
heuristischeSuche(Pfad,Pfade,Ziel,Loesung):-
Pfad=pfad([KnotenA|RestPfadA],KostenA),
findall(pfad([KnotenN,KnotenA|RestPfadA],KostenN),
(verbunden(KnotenA,KnotenN),
not(member(KnotenN,[KnotenA|RestPfadA])),
bewerte_heuristisch(KnotenA,KostenA,KnotenN,KostenN)),
GefundenePfade),
sortiere_gefPfade_ein(GefundenePfade,Pfade,NeuePfade),
NeuePfade=[PfadN|RestPfade],
heuristischeSuche(PfadN,RestPfade,Ziel,Loesung).
Aufgabe
Mit Hilfe obigen Programms und des trace-Modus bzw. passend eingefügter write-Anweisungen
ist wie in der Breitensuche ein graphischer "Trace" der
Anfrage
?- heuristischeSuche(e,i,L). herzustellen.
Lösung
