A* Algorithmus Visualisierer

Pseudocode

A* ist Dijkstra mit einem zusätzlichen Term. Wo Dijkstra stets den Knoten mit den kleinsten bestätigten Kosten g ausdehnt, nimmt A* den mit dem kleinsten f = g + h, wobei h die noch verbleibenden Kosten schätzt. Setzt man h überall auf null, wird der Pseudocode unten exakt zu Dijkstra.

A*(graph, start, ziel, h):
    für jeden Knoten v: g[v] = unendlich
    g[start] = 0
    f[start] = h(start)
    offen = Prioritätswarteschlange mit (f[start], start)
    geschlossen = leere Menge

    solange offen nicht leer ist:
        u = offen.extractMin()        // kleinstes f
        wenn u == ziel: gib rekonstruiere(u) zurück
        füge u zu geschlossen hinzu

        für jede Kante (u, v, w):
            wenn v in geschlossen: überspringe
            versuch = g[u] + w
            wenn versuch < g[v]:
                vorgänger[v] = u
                g[v] = versuch
                f[v] = versuch + h(v)
                offen.einfügen(f[v], v)

    gib kein Pfad zurück

Das Überspringen der geschlossenen Menge in Zeile 15 ist nur sicher, wenn h konsistent ist, also h(u) <= w(u, v) + h(v) für jede Kante gilt. Bei einer lediglich zulässigen Heuristik müssen Knoten die geschlossene Menge wieder verlassen dürfen, sonst kann A* einen nicht optimalen Pfad liefern. Der Visualisierer oben skaliert die Luftlinie mit den günstigsten Kosten pro Einheit, die irgendeine Kante bietet. Dadurch wird h über die Dreiecksungleichung konsistent, und ein Wiederöffnen ist nicht nötig.

Durchgerechnetes Beispiel, Schritt für Schritt

Fünf Knoten, S im Ursprung und das Ziel G fünf Einheiten rechts davon. Der Kern der Spur ist der Knoten, den A* nie anfasst.

Beispielgraph: S(0,0), A(2,1), B(2,-1), C(1,4), G(5,0). Kanten S-A = 3, S-B = 2, S-C = 4, A-B = 2, A-G = 4, B-G = 6, C-G = 7. Skaliert man die Luftlinie mit den günstigsten Kosten pro Einheit einer Kante (0,894), ergibt sich h(S) = 4,47, h(A) = 2,83, h(B) = 2,83, h(C) = 5,06, h(G) = 0.

1. 1. Dehne S aus, den einzigen offenen Knoten, bei f = 4,47. Das Relaxieren der drei Kanten setzt A auf g = 3, f = 5,83; B auf g = 2, f = 4,83; und C auf g = 4, f = 9,06. C wirkt schon jetzt teuer: nahe an S, aber vom Ziel weg gerichtet.
2. 2. Dehne B aus, jetzt das kleinste f mit 4,83. Es erreicht das Ziel mit g = 8, f = 8,00. Beachte: A* hört hier nicht auf. Das Ziel zu finden ist nicht dasselbe wie es auszudehnen, und 8 ist noch nicht als bester Wert bekannt.
3. 3. Dehne A bei f = 5,83 aus. Seine Kante zu G ergibt g = 7 und schlägt damit die 8 über B, sodass sich G auf f = 7,00 verbessert.
4. 4. Dehne G bei f = 7,00 aus, dem kleinsten f in der offenen Menge. Das Ziel ist ausgedehnt, seine Kosten stehen endgültig fest, und die Suche endet, während C mit f = 9,06 unberührt in der offenen Menge liegt.

A* liefert S nach A nach G zu Kosten von 7 und hat dabei 4 Knoten ausgedehnt. Dijkstra liefert auf demselben Graphen denselben Pfad zu denselben Kosten, dehnt aber 5 aus: er arbeitet C ab, bevor er bereit ist, das Ziel festzuschreiben. C war nie einen Besuch wert, und h ist der Grund, warum A* das wusste, ohne nachzusehen.

Komplexität und woher sie kommt

Zeit: O((V + E) log V) im schlechtesten Fall mit einem binären Heap · Speicher: O(V)

Der schlechteste Fall ist der von Dijkstra, und zwar aus demselben Grund: jeder Knoten kann einmal in die Prioritätswarteschlange gelangen und jede Kante einmal ein Decrease-Key auslösen, also V Entnahmen und E Aktualisierungen zu je O(log V). Die Heuristik ändert an dieser Schranke nichts. Sie ändert die Konstante: Knoten, deren f die endgültigen Kosten des Ziels übersteigt, werden nie ausgedehnt. Mit h = 0 entartet A* exakt zu Dijkstra; mit perfektem h läuft er direkt den optimalen Pfad entlang. Über 4000 zufällig erzeugte gewichtete Graphen dehnte die obige Implementierung im Mittel 4,58 Knoten aus gegenüber 5,52 bei Dijkstra und lieferte jedes Mal die optimalen Kosten.

Wann A*-Algorithmus passt und wann nicht

A* lohnt seinen Mehraufwand nur, wenn es ein Ziel und eine brauchbare Schätzung der Entfernung dorthin gibt. Fehlt eines von beiden, ist eines der folgenden Verfahren das bessere Werkzeug.

Häufige Fehler

• Eine überschätzende Heuristik zerstört die Optimalität. Kann h die echten Restkosten übersteigen, schreibt A* das Ziel womöglich über eine nicht günstigste Route fest, und zwar stillschweigend. Die Luftlinie ist nur zulässig, wenn sie dieselbe Einheit wie die Kantengewichte hat. Pixelabstand gegen Gewichte von 1 bis 10 überschätzt massiv.
• Zulässig ist nicht dasselbe wie konsistent. Die geschlossene Menge setzt Konsistenz voraus, also h(u) <= w(u, v) + h(v) für jede Kante. Eine zulässige, aber inkonsistente Heuristik verlangt, dass Knoten wieder geöffnet werden, wenn eine günstigere Route auftaucht, sonst kann der gelieferte Pfad suboptimal sein.
• Abbrechen, sobald das Ziel entdeckt wird. Das Ziel beim Relaxieren zu erreichen beweist nichts. In der Spur oben findet B das Ziel mit Kosten 8, einen Schritt bevor A es mit 7 findet. Man muss warten, bis das Ziel der ausgedehnte Knoten ist.
• h bei jedem Vergleich neu berechnen. Die Heuristik wird einmal pro Knoten aufgerufen, nicht einmal pro Vergleich in der Prioritätswarteschlange. h neben g zwischenzuspeichern entscheidet darüber, ob sich die Heuristik rechnet oder mehr kostet als sie spart.
• Annehmen, A* schlage Dijkstra immer. Mit schwacher Heuristik dehnt A* dieselben Knoten aus wie Dijkstra, plus den Aufwand für h. Auf Graphen ohne Geometrie ist h = 0 die ehrliche Wahl, und Dijkstra ist die einfachere Implementierung.

Häufig gestellte Fragen

Was bedeutet f = g + h eigentlich?

g ist, was ein Pfad zu diesem Knoten bisher gekostet hat, und das ist eine Tatsache. h ist eine Schätzung, was der Weg von hier zum Ziel kosten wird. Ihre Summe f ist die geschätzte Gesamtlänge der günstigsten Route durch diesen Knoten, und A* arbeitet immer am Knoten mit der kleinsten Schätzung.

Was macht eine Heuristik zulässig?

Sie überschätzt die echten Restkosten nie. Die Luftlinie erfüllt das für Bewegung in der Ebene, weil keine Route kürzer als eine Gerade sein kann. Zulässigkeit ist genau das, was garantiert, dass A* einen optimalen Pfad liefert.

Ist A* immer schneller als Dijkstra?

Er dehnt bei gleichem Graphen und konsistenter Heuristik nie mehr Knoten aus als Dijkstra und meist weniger. Asymptotisch schneller ist er aber nicht: beide sind O((V + E) log V). Der Gewinn ist ein konstanter Faktor und schrumpft auf null, je schwächer die Heuristik in Richtung null wird.

Kann A* negative Kantengewichte verarbeiten?

Nein. Er erbt die Annahme, die Dijkstra funktionieren lässt, nämlich dass das Verlängern eines Pfades ihn nie billiger macht. Nutze Bellman-Ford, wenn Gewichte negativ sein können.

Wer hat A* erfunden?

Peter Hart, Nils Nilsson und Bertram Raphael am Stanford Research Institute, in einer Arbeit von 1968 mit dem Titel "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". Eine Notiz derselben Autoren von 1972 korrigierte die ursprüngliche Optimalitätsaussage und trennte Zulässigkeit von Konsistenz.

Warum hat A* im Durchlauf oben den Knoten C übersprungen?

C liegt bei f = 9,06, während das Ziel bei f = 7,00 festgeschrieben wurde. Weil die Heuristik nie überschätzt, ist ein f von 9,06 die Zusage, dass keine Route über C weniger als 9,06 kosten kann, und das ist bereits schlechter als eine fertige Antwort von 7. A* darf ihn verwerfen, ohne nachzusehen.