Graphen	Tiefensuche Breitensuche Heuristische Suche Haus des Nikolaus Bauer,Kohl,Wolf,Ziege Missionare und Kannibalen Pfad: Startseite / Fächer / Informatik / Prolog / Graphen / Heuristische Suche
Autor: mk 03.04.2007 12:44:00 1426	Heuristische Suche

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