Benutzer:Sargeras/sandbox

nützliche Links

• Wikipedia Autoreviewer
• Wikipedia Page History Statistics
• Edit Counter

A* Algorithmus - TODO

Algorithmus A

Wie lautet der, wie wurde er zu A*?

A* Algorithmus

• merkt man sich zu jedem knoten den f wert kann man vergleichen und bei geringerem wert updaten, somit wird die closed list überflüssig - man hat aber nicht in allen fällen alle knoten des graphen, vielleicht erst zur suchzeit generiert, eventuell lässt sich die closedlist effizienter implementieren als jeden einzelnen knoten zusammen mit f wert zu speichern (nur speichern von eigenschaften, klassen von knoten)
• Kosten von Knoten und Kanten besser voneinander abgrenzen (einmal Kosten von Start-Knoten, einmal Kosten der Kante)
• im Fall der Wegsuche kann man die Closed List durch Speicherung der f Werte in allen Knoten simulieren

Die Besonderheit an A-Star ist, dass er nicht nur grundsätzlich Kosten berücksichtigt,
sondern während seiner Laufzeit kontinuierlich Schätzungen über die Restdistanz anfertigt.
Anhand dieser Schätzungen wird bestimmt, welcher Knoten am Günstigsten erscheint und
folglich als Nächstes gewählt wird.

Idee des Algorithmus

fertig

Funktionsweise

fertig (Anmerkung zur Closed List ersetzen)

Anmerkung: Die Closed List kann unter bestimmten Voraussetzungen entfallen. Siehe hierzu den Abschnitt Baumsuche, Graphsuche.

Anwendungsgebiete

fertig

Beispiel

fertig

Baumsuche, Graphsuche

diesen Abschnitt unter Funktionsweise/Anmerkung mit siehe auch verlinken

ohne Closed List auch rückwärts laufen, im Baum gibts das nicht, Terminierungsproblem bei Baumsuche im Graph

im graph geht man keine kreise (-> closed list)
im baum gibts keine kreise (-> man brauch auch keine closed list)

Die Closed List kann auch indirekt implementiert werden. Dazu speichern auch die abschließend untersuchten Knoten ihren f Wert. Wird nun ein abschließend untersuchter Knoten erneut gefunden, ist sein alter f Wert geringer als der neue, da der kürzeste Weg zu diesem Knoten bereits gefunden wurde. Der Knoten wird also nicht erneut in die Open List eingefügt.

Wird keine Closed List benutzt, muss anderweitig sicher gestellt werden, dass Knoten nicht mehrfach untersucht werden. Ansonsten wird die worst-case Laufzeit schlechter als quadratisch. Außerdem terminiert der Algorithmus nicht mehr, wenn es keine Lösung gibt. Die Knoten werden dann unendlich oft untersucht, da die Open List nie leer wird.

Heuristiken

nur zulässig -> muss Baumsuche machen

also immer monotone heuristiken verwenden wenns geht, hat man mehrere monotone heuristiken zur auswahl, immer die beste nehmen, um möglichst wenig knoten zu expandieren (berechnungskosten der heuristik ist im allgemeinen vernachlässigbar) - das beispiel der perfekten heuristik bringt nix (ausgangsproblem), da wird ja offensichtlich nix vereinfacht (und heuristiken basieren auch vereinfachungen/mindestkosten schätzungen)

Eigenschaften

fertig

Optimalität

Beweis aus Russel/Norvig ersetzen durch Beweis, dass zu einem expandierten Knoten auch der optimale Pfad bekannt ist.

Der Zielknoten ist ein solcher Knoten und wäre mit diesem Beweis ebenfalls abgedeckt. Beim Russel/Norvig Beweis ist nicht sofort einzusehen, warum der bessere Weg gefunden werden muss. Es könnte ja sein, dass ein Knoten schon auf der Closed List ist (siehe Beispiel unter zulässige Heuristik) und den besten Pfad blockiert.

Zeitkomplexität

Schön vereinfachende Annahmen benutzen:

• Fibonacci-Heap mit amortisiert konstanter Laufzeit in O Notation einsetzen
• Heap-Find entfällt bei Mitführen eines Zeigers auf das Heap-Element
• ...

Dann ist die Laufzeit bestimmt linear bezüglich der Länge der Lösung. Das widerspricht aber garantiert der in Russel-Norvig zitierten Aussage, dass exponentielles Wachstum auftritt, sobald der Fehler in der Heuristik einen bestimmten Wert überschreitet.

Abschnitt löschen? Behalten, obwohl keine klare Aussage drin steht?

Anzahl ausgehender Kanten beschränken: braucht man nicht, Schleifen aufdröseln und getrennt betrachten (so wie im Dijkstra Artikel)

Nachteile

fertig

Verwandte Algorithmen

Vergleich mit dem Algorithmus von Dijkstra und einem Greedy-Algorithmus

Dieser Vergleich bedarf möglicherweise einer Überarbeitung. Die dargestellte Version des Greedy-Algorithmus entspricht nicht der in Wikipedia enthaltenen Version. Näheres ist auf den Diskussionsseiten der entsprechenden Algorithmen zu finden: A*, Dijkstra und Greedy. Hilf bitte mit, die Ungereimtheiten zu beseitigen.

Beispielgraph, die Knoten sind mit der geschätzten Restdistanz bis zum Ziel beschriftet, die Kanten mit ihren Kosten Alle drei Algorithmen benutzen eine Open List (bekannte Knoten, die noch nicht abschließend besucht sind) Closed List (Knoten, die abschließend besucht sind) Knoten auf der Closed List werden in keinem Fall erneut besucht. Es wird immer der Knoten mit dem niedrigsten $f$ Wert besucht. Der einzige Unterschied liegt in der Definition der Bewertungsfunktion $f$. A*-Algorithmus: $f=g+h$ Algorithmus von Dijkstra: $h=0$, also $f=g$ Greedy-Algorithmus: $g=0$, also $f=h$ In den Diagrammen ist für Knoten auf der Open List jeweils der $f$ Wert angegeben. Bereits bekannte Knoten zeigen auf ihren Vorgänger.

A*	Dijkstra	Greedy
Schritt 1: Der Startknoten wurde abschließend besucht.	Schritt 1: Der Startknoten wurde abschließend besucht.	Schritt 1: Der Startknoten wurde abschließend besucht.
Schritt 2: Der Knoten in der Nähe der Verbindungslinie Start–Ziel wurde abschließend besucht. Hier zeigt sich das zielgerichtete Suchen von A*.	Schritt 2: Der Knoten mit geringstem Abstand vom Startknoten wurde abschließend besucht. Hier zeigt sich das kreisförmige Suchverhalten von Dijkstra.	Schritt 2: Der Knoten mit geringstem Abstand (Schätzung) zum Zielknoten wurde abschließend besucht. Der Greedy-Algorithmus sucht wie A* zielgerichtet.
Schritt 3: Der Vorgängerzeiger von Knoten C zeigt nun auf Knoten B. Der $f$ Wert wurde verringert.	Schritt 3: Knoten A wurde abschließend besucht. Der Open List wurden keine neuen Knoten hinzugefügt.	Schritt 3: Knoten B hatte einen größeren $f$ Wert als Knoten C. Daher wurde Knoten C abschließend besucht. Der Algorithmus ist gierig und versucht möglichst schnell eine Lösung zu finden. Der kürzere Weg über Knoten B wird übersehen.
Schritt 4: Der einzige Knoten auf der Open List wurde abschließend besucht.	Schritt 4: Der einzige Knoten auf der Open List wurde abschließend besucht.	Schritt 4: Ein suboptimaler Weg wurde gefunden. A* und Dijkstra haben noch keine Lösung gefunden.
Schritt 5: Der optimale Weg wurde gefunden.	Schritt 5: Der optimale Weg wurde gefunden.

Quellen

• A* und Greedy: Artificial Intelligence – A Modern Approach (Stuart Russell, Peter Norvig)
• Dijkstra: Wikipedia und verschiedene Internetseiten (Amit's A* Pages)

Einzelnachweise

erstes ref tag ein bisschen text mit einem anderen ref tag. und schließlich die verwendung eines bereits bekannten ref tags.

neuer abschnitt mit ref zu lee killough.

Gelöschte Abschnitte aus dem alten A*-Algorithmus Artikel

Diese gelöschten Abschnitte sind hier geparkt, weil sie sinnvolle Passagen oder Ideen enthalten, die ich noch in den aktuellen A*-Artikel integrieren will.

Nicht-monotone Heuristik => Closedlist

Die aufgestellte Behauptung ist falsch!

Anmerkung: Neben der hier vorgestellten Methode den A*-Algorithmus zu implementieren gibt es häufig auch noch Implementierungen welche eine sogenannte Closed List von bereits besuchten Knoten mitführen welche sie in jedem Schritt überprüfen. Dies ist nötig falls eine Heuristik verwendet werden soll welche zwar zulässig aber nicht monoton ist. Da diese Implementierung jedoch davon ausgeht, dass eine monotone Heuristik verwendet wird, ist der erste genutzte Pfad der zu einem beliebigen Knoten welcher expandiert wird führt auf jeden Fall auch der kürzeste Pfad zu diesem Knoten. Somit ist es nicht nötig die Pfadkosten entdeckter Knoten eventuell später ein zweites mal mit den Pfadkosten, welche die Knoten bei ihrer ersten Entdeckung hatten, zu vergleichen, da die Pfadkosten bei der ersten Entdeckung garantiert niedriger waren. Die genauen Unterschiede zwischen einer monotonen Heuristik und einer zulässigen Heuristik findet man weiter unten unter Heuristiken im Artikel.

Heuristik und Laufzeit

Die gewählte Heuristik hat ebenfalls große Auswirkungen auf die Laufzeit des A*-Algorithmus. Auf der einen Seite gibt es die perfekte Heuristik, welche in jedem Schritt die tatsächlichen Kosten für einen Knoten bis zum Ziel als Schätzwert abgibt, wodurch der A*-Algorithmus nur die Knoten erkunden wird, welche auch tatsächlich auf dem kürzesten Pfad liegen. Eine solch genaue Heuristik ist aber sinnlos, und in der Berechnung extrem teuer, da man für sie erst einmal für jeden Knoten den kürzesten Pfad bis zum Ziel finden muss, was genau der ursprünglich zu lösenden Problemstellung entspricht. Auf der anderen Seite gibt es extrem schlechte aber dafür sehr einfach zu berechnende Heuristiken. So kann man die Entfernung zwischen zwei Knoten mit Kosten von 0 schätzen, wodurch effektiv gar keine Heuristik mehr verwendet wird, und der A*-Algorithmus alle Knoten blind untersuchen muss, bis er irgendwann auf diese Weise das Ziel findet. Diese Version des Algorithmus ist besser als der Algorithmus von Dijkstra bekannt. Eine gute Heuristik stellt somit einen Kompromiss zwischen dem Berechnungsaufwand für die Heuristik und ihrer Genauigkeit dar.

Graphtraversierung

aus Traversierung:

Traversierung ist in der Graphentheorie der Name für Verfahren, die eine Route bestimmen, bei der jeder Knoten und jede Kante eines baumförmigen Graphen genau einmal besucht wird. Für Binärbäume existieren spezielle Traversierungen, die man als Linearisierung bezeichnet.

• man kann aber auch nicht baumförmige Graphen traversieren
• bei Baumsuche werden Knoten mehrfach besucht (unendliche Traversierung, es muss ein Abbruchkriterium geben, z.B. Weg gefunden)

neuen Artikel erstellen? Baumsuche/Graphsuche (im Hinblick auf A*-Algorithmus Artikel) erklären