A* verständlich erklärt

Wer in einem Straßennetz den kürzesten Weg sucht, muss entscheiden, welche Kreuzung er als Nächstes ansieht. Das Verfahren A* entscheidet nach dem bisherigen Weg plus einer Schätzung des Rests. Diese Seite zeigt zuerst ohne Formeln, warum diese Mischung den kürzesten Weg findet und dabei weniger Kreuzungen ansieht als die Suche nach dem bisherigen Weg allein, und danach mit Modell, Formeln, Messwerten und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Welche Kreuzung sehe ich als Nächstes an?

Sie sollen für einen Lieferwagen den kürzesten Weg vom Lager zu einem Kunden finden. Das Viertel besteht aus Kreuzungen und Straßen, einige Straßen sind gesperrt. Sie kennen die Wege nicht im Voraus und erkunden das Viertel Kreuzung für Kreuzung.

Dabei führen Sie eine Merkliste. Jede Kreuzung, die Sie erreichen können, aber noch nicht angesehen haben, kommt darauf. In jedem Schritt nehmen Sie eine Kreuzung von der Liste und schauen sich ihre Nachbarkreuzungen an. Alles hängt an der Wahl: Welche Kreuzung nehmen Sie von der Liste?

Die Demo (ein Programm zum Ausprobieren im Browser) spielt das auf einem Straßenraster mit gesperrten Feldern durch und vergleicht drei Regeln für diese Wahl.

Drei Regeln für die Wahl

• Nur die geschätzte Reststrecke. Sie nehmen die Kreuzung, die laut Luftlinie dem Kunden am nächsten liegt. Die Luftlinie ist eine Schätzung des Rests: Keine Straße kann kürzer sein als die gerade Strecke. Liegt der Kunde hinter einer Sperre, läuft die Suche bis zur Sperre, muss zurück und liefert einen Umweg.
• Nur der bisherige Weg. Sie nehmen die Kreuzung, die Sie vom Lager aus bisher am billigsten erreicht haben. Diese Regel findet den kürzesten Weg, sieht sich aber in alle Richtungen um, auch weg vom Kunden. Die angesehenen Kreuzungen bilden in der Demo einen Kreis um das Lager.
• Beides zusammen. Sie addieren für jede Kreuzung den bisherigen Weg und die geschätzte Luftlinie zum Kunden und nehmen die Kreuzung mit der kleinsten Summe. Dieses Verfahren heißt A* (gesprochen „A-Stern“).

Warum die Mischung trägt

Die Summe schätzt die Länge des ganzen Wegs, der über diese Kreuzung führt. Eine Kreuzung dicht am Kunden, die Sie nur über einen langen Umweg erreichen, hat eine große Summe und wartet. Eine Kreuzung dicht am Lager, aber in der falschen Richtung, hat ebenfalls eine große Summe. Zuerst kommen die Kreuzungen dran, die auf einem kurzen Gesamtweg liegen könnten.

Die angesehenen Kreuzungen bilden in der Demo deshalb ungefähr ein Oval um die Luftlinie zwischen Lager und Kunde, weder einen schmalen Streifen noch einen Kreis. Nur nach der Schätzung zu wählen führt in Sackgassen, nur nach dem bisherigen Weg zu wählen sieht zu viel an. Die Summe gleicht beides aus.

Der gefundene Weg ist der kürzeste, solange die Schätzung nie größer ist als der wahre Rest. Die Luftlinie erfüllt das, weil keine Straße kürzer sein kann als die gerade Strecke.

Wie viel vom Tempo bleibt?

In den Beispielen der Demo sieht A* höchstens so viele Kreuzungen an wie die Regel mit dem bisherigen Weg allein. Die reine Luftlinien-Regel sieht im Mittel weniger an, liefert dafür aber teils Umwege. Im Mittel liegt A* bei der Zahl der angesehenen Kreuzungen zwischen den beiden anderen Regeln; die genauen Zahlen stehen weiter unten auf dieser Seite.

Warum es nicht mehr Tempo gibt, zeigt die Demo nur teilweise. Im Raster der Demo darf man nur nach oben, unten, links oder rechts fahren, und gesperrte Felder erzwingen Umwege. Die Luftlinie ist dort kürzer als der wahre Weg. Die Messungen sprechen dafür, dass das eine Rolle spielt: Bei sehr vielen gesperrten Feldern, wo die Luftlinie am weitesten unter dem wahren Weg liegt, bricht der Vorteil von A* gegenüber der gründlichen Regel ein, dazwischen bleibt er ungefähr gleich. Mit einer exakten Schätzung sähe A* in einem Test nur die Kreuzungen des besten Wegs an; dazwischen hat die Demo nichts gemessen.

Für den Betrieb: Fragen Sie den Anbieter einer Routenplanung, wie der Restweg geschätzt wird und ob die Schätzung nie größer ist als der wahre Rest. Gilt das, bleibt der Weg der kürzeste, auch wenn die Schätzung grob ist; die Suche sieht dann nur mehr Kreuzungen an.

Wie ernst ist das Modell zu nehmen?

Die Demo rechnet auf erfundenen Rastern ohne Diagonalen, Einbahnstraßen und Zeitfenster und zeigt, wie die Regeln suchen; wie sich echte Straßennetze verhalten, zeigt sie nicht.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Instanz und Graph: ein gestörtes Raster mit Hindernissen, Vierer-Nachbarschaft (keine Diagonalen); das Kantengewicht ist der echte euklidische Abstand, was die Heuristik automatisch zulässig macht. Dazu eine handgebaute 8-Knoten-Falle. Graph und Instanz sind wortgleiche Kopien aus der greedy-best-first-demo.
• Suchkern: eine gemeinsame Prioritätswarteschlange für drei Suchen, nur die Priorität unterscheidet sich: Greedy Best-First Search (GBFS) nach \(h(n)\), Uniform-Cost-Search (UCS) nach \(g(n)\), A* nach \(g(n)+h(n)\). Findet A* einen billigeren Weg zu einem noch nicht expandierten Knoten, bekommt der Knoten den besseren Elternknoten (klassische Dijkstra-Relaxation, nötig für die Optimalität); GBFS behält den ersten.
• Regler: Instanz (Raster oder handgebaute Heuristik-Falle), Rastergröße (5–25), Hindernisdichte (0–40 %), Zufalls-Seed der Instanz. A* bringt keine eigenen Regler, kein Bewertungsbudget und keinen Ketten-Seed mit; die Suche ist vollständig deterministisch.

Die Formeln

Die Heuristik ist der geradlinige Abstand zum Ziel, \(h(n) = \lVert xy_n - xy_{\text{Ziel}} \rVert_2\); sie ist zulässig, weil die Kantengewichte echte euklidische Abstände sind (Dreiecksungleichung). Die drei Suchen unterscheiden sich nur in der Priorität, bei A* ist sie:

\[f(n) = g(n) + h(n)\]

Ist \(h\) zulässig, überschätzt sie also den wahren Restweg \(h^*(n)\) nie, findet A* einen kürzesten Pfad:

\[h(n) \le h^*(n)\]

Der Suchkern führt eine Menge bereits expandierter Knoten ohne Wiedereröffnung. Dafür braucht die Optimalität Konsistenz, \(h(n) \le c(n,m) + h(m)\) für jede Kante von \(n\) nach \(m\) mit Kosten \(c(n,m)\); sie folgt hier aus der Dreiecksungleichung. Für bloße Zulässigkeit gilt die Aussage nur mit Wiedereröffnung. Das ist Standardwissen der Theorie, nicht der README entnommen. Zwei Sonderfälle sind im Test nachgewiesen: \(h \equiv 0\) ergibt exakt UCS; \(h = h^*\) ergibt auf der Testinstanz eine Suche, die nur die Knoten des optimalen Pfads expandiert. Wie viel A* vom Effizienzvorsprung der Greedy-Suche behält, misst die Demo mit \(E\) als Zahl der Knoten-Expansionen:

\[\dfrac{E_{\text{UCS}} - E_{\text{A*}}}{E_{\text{UCS}} - E_{\text{GBFS}}}\]

Als Erklärung dient die Heuristik-Enge \(h(\text{Start}) / L_{\text{opt}}\), also der Abstand des Startknotens zum Ziel im Verhältnis zur Länge des tatsächlich kürzesten Wegs (1,0 = perfekte Schätzung).

Befunde

Alle Zahlen gelten für Rastergröße 12 und Hindernisdichte 15 %, sofern nicht anders angegeben, als Mittel über 5 feste Instanzen (Zufalls-Seeds 100000–100004); die Läufe sind vollständig deterministisch. Das Effizienzverhältnis ist die Zahl der UCS-Expansionen geteilt durch die der jeweiligen Suche (größer als 1 heißt effizienter als UCS).

Frage	Befund
Ist A* optimal?	Ja, die Lücke beträgt 0,0 % bei jeder gemessenen Hindernisdichte und Rastergröße. A* findet denselben Pfadwert wie UCS über 40 Zufallsinstanzen mit 0–40 % Hindernissen, auf kleinen Instanzen auch gegen die vollständige Enumeration aller einfachen Pfade.
Behält A* den Effizienzvorsprung von GBFS?	Nur teilweise: 32 % im Standardfall. Verhältnis gegenüber UCS 1,38x für A* gegen 4,99x für GBFS; mittlere Expansionen 90 (A*), 24 (GBFS), 121 (UCS). Die Verhältnisse sind laut Auswertungscode Mittel der Einzelverhältnisse und daher nicht der Quotient der gerundeten Mittel. Die Vorab-Hypothese „A* behält den Großteil“ ist damit widerlegt.
Hindernisdichte 0/10/20/30/40 %	A*: 1,47/1,52/1,54/1,49/1,20x, flach bis 30 %, Einbruch bei 40 %. GBFS: 6,26/5,58/4,55/3,21/1,92x, monoton fallend.
Rastergröße 6/10/14/18/22	A*: 1,38/1,45/1,56/1,46/1,39x, wächst nicht mit der Größe. GBFS: 2,8/4,1/6,0/7,7/8,5x.
Wie eng ist die Heuristik?	h(Start) / wahrer Weg = 0,81 bei 0 % Hindernissen, 0,76 bei 15 %, 0,61 bei 40 %. Die Enge sinkt mit der Hindernisdichte; A*s Verhältnis bricht erst bei 40 % ein, dazwischen ist es flach. Die Messungen sprechen dafür, dass eine lockere Heuristik die Suche verbreitert; die Heuristik wurde nicht kontrolliert variiert.
Expandiert A* je mehr Knoten als UCS?	Nie (60 Zufallsinstanzen im Test plus alle Sweep-Instanzen).
Handgebaute Heuristik-Falle	GBFS liegt 7,47 % über dem Optimum (6 Expansionen); A* und UCS sind beide optimal (7 bzw. 8 Expansionen).
Einzelne Voreinstellungs-Instanz (Zufalls-Seed 35)	GBFS-Lücke 22,53 %, A*-Effizienz 1,54x, GBFS-Effizienz 5,48x, behaltener Anteil 43 %. Das weicht vom Sweep-Mittel (1,38x) ab; belastbar sind laut README die Mittelwerte.

Grenzen

• Der Vorsprung kostet die Garantie: Der größere Teil von GBFS' Effizienzvorsprung geht mit der Optimalitätsgarantie verloren, und A*s Vorsprung wächst nicht mit der Instanzgröße (1,38x bei Größe 6, 1,39x bei 22), GBFS' schon (2,8x bis 8,5x).
• Vermutlich begrenzt die Heuristik, nicht der Algorithmus: Getestet sind nur die Sonderfälle \(h \equiv 0\) und \(h = h^*\). Mit dem exakten Restweg als \(h\) expandiert A* im Test (eine Instanz) nur die Knoten des optimalen Pfads. Dazwischen liegt der ganze Spielraum besserer Heuristiken, die in der Demo nicht gebaut werden.
• Kein monotoner Verlauf: Anders als bei GBFS sinkt A*s Vorsprung nicht gleichmäßig mit den Hindernissen; er ist flach bis 30 % und bricht bei 40 % ein, wo die Heuristik am lockersten ist.
• Speicher ist unbegrenzt: A* hält die gesamte Grenzmenge, auf riesigen Graphen das eigentliche Problem.
• Heuristik nötig: Ohne brauchbare Heuristik (\(h \equiv 0\)) reduziert sich A* exakt auf UCS. Die Optimalität hängt an der Zulässigkeit der Heuristik.
• Synthetische Instanzen: ein Raster mit Jitter, Vierer-Nachbarschaft, keine Zeitfenster, keine gerichteten Kanten. Verglichen werden Knoten-Expansionen, keine Rechenzeiten.

Quellen

• Hart, P. E., Nilsson, N. J., & Raphael, B. (1968): A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics 4(2), 100–107.
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/astar-demo.

Die genannte Arbeit wurde für diese Seite nicht nachgeschlagen; der Literaturhinweis stammt aus der README der Demo.