Upload
klemens-graf
View
217
Download
1
Embed Size (px)
Citation preview
Der A*-Algorithmus
Gliederung1.Uniformierte Suche2.Heuristische Suche
a) Kostenfunktion b) Heuristische Funktion c) Schätzfunktion
2.1.A*-Algorithmus
4.Beispiel5.Bemerkungen6.Verbesserungen7.Zusammenfassung
Uniformierte SucheBreitensuche
Vorteil : Findet Lösung mit minimaler WeglängeNachteil: Suchbaum wächst exponentiell mit der Suchtiefe
Tiefensuche
Vorteil : Speicherplatzbedarf ist linearNachteil: Findet kürzesten Weg eher zufällig (blinde Suche)
Heuristische Suche Die Kostenfunktion g : - ordnet jedem Knoten ein Gewicht g(k) 0 zu
- heißt streng monoton, wenn g(k1) < g(k2) für alle Knoten k1, k2 gilt
- gibt Aufschluss über die Höhe des Suchaufwand vom Startknoten bis zum jeweiligen Knoten des Suchbaumes
Die heuristische Funktion h
- ordnet jedem Knoten k im Suchraum eine nicht negative Zahl h(k) zu - 0 ≤ h(k) ≤ h*(k)
- h(k) überschätzt nie die Kosten
- Es gilt h(e) = 0 (Zielknoten)
- Schätzfunktion sollte eine möglichst hohe untere Schranke sein
Schätzungen
City-Block- bzw. Manhattan-Abstand:
Euklidischer Abstand:
Schätzfunktion f
Der A* - Algorithmus vereint die Kostenfunktion g unddie heuristische Funktion h.
f(k) = g(k) + h(k) wobei g eine streng monotone Kostenfunktion und h einezulässige heuristische Funktion ist.
Eigenschaften - korrekt, d.h. das Suchergebnis, das die A* -Suche liefert, ist eine
Lösung des Suchproblems.
- vollständig, d.h. wenn es eine Lösung des Suchproblems existiert, so wird diese auch gefunden.
- optimal, d.h. dass die Lösung des Suchproblems der kürzeste Pfad zum Zielknoten ist.
- optimal effizient, d.h. jeder andere optimale und vollständige Algorithmus, der die selbe Heuristik verwendet, muss mindestens so viele Knoten betrachten wie A*, um eine Lösung zu finden.
Algorithmus
1- Erzeuge eine Menge OPEN und vereine sie mit dem Startknoten 2- Erzeuge eine leere Menge CLOSED
3- Berechne für jeden Knoten aus der Menge OPEN den Schätzwert f(k)
4- Wähle denjenigen Knoten aus der Menge OPEN mit dem kleinsten Schätzwert
5- Weiter mit 3)
6- Ist die OPEN Menge leer, so ist das Problem unlösbar
Soll außer der Länge des kürzesten Pfades auchder Pfad selbst gefunden werden, so kommt einweiterer Schritt hinzu : 7- Es wird die Funktion Gib_kürzesten_Pfad_aus aufgerufen
BeispielAugsburg: 43 kmErfurt: 342 kmFrankfurt: 353 kmKarlsruhe: 260 kmKassel: 446 kmMannheim: 311 kmMünchen: 0 kmNürnberg: 151 kmStuttgart: 199 kmWürzburg: 229 km
1.Frankfurt wurde erkundet, als nächstes wird Mannheim untersucht.
2.Mannheim wurde erkundet, als nächstes wird Karlsruhe untersucht.
3.Karlsruhe wurde erkundet, als nächstes wird Würzburg untersucht.
4. Würzburg wurde erkundet, stellte sich aber als eine schlechte Wahl dar, und es wird wieder der ursprüngliche Pfad durch Augsburg verfolgt.
5. Augsburg wurde erkundet und es wurde ein Weg nach München gefunden der jedoch eventuell länger als nötig ist.
6.Nürnberg wurde erkundet, und es wurde ein kürzester Pfad nach München gefunden.
Bemerkungen Der Algorithmus funktioniert nur wenn folgendeBedingungen erfüllt sind: - Jeder Knoten hat nur endlich viele Nachfolger
- Die Heuristikfunktion h überschätzt für keinen Zustand z die Kosten einer Operationenfolge
- keine negativen Gewichte der Knoten
VerbesserungenEine Möglichkeiten den Algorithmus zu verbessern ist zum Beispiel dasBenutzen einer Heuristik h1 mit h(k) h1(k)
Zusammenfassung
Quellenhttp://www.geosimulation.de/umsetzungen/Beschreibungen/
Routenoptinierung_A_Stern_Algorithmus.htm
http://a-stern-algorithmus.lexikona.de/art/A-Stern-Algorithmus.html
http://de.wikipedia.org/wiki/A-Stern-Algorithmus
http://wiki.delphigl.com/index.php/A-Stern
http://www2.informatik.uni-erlangen.de/Lehre/WS200506/GameAlgHS/download/Baur-AStar.pdf?language=de
http://fuzzy.cs.uni-magdeburg.de/studium/ise/txt/ise05k09.pdf