Heuristiken & Pfadsuche: Von Dijkstra zu A*
Wie A* funktioniert — und warum Dijkstra ohne Heuristik schnell langweilig wird.
Dein GPS findet die schnellste Route durch Millionen von Kreuzungen in Millisekunden. Es prüft nicht jede mögliche Route — schon für eine Lieferfahrt mit nur 21 Stopps gäbe es mehr mögliche Reihenfolgen als Sekunden seit dem Urknall. Stattdessen nutzt es eine mathematische Abkürzung: eine Heuristik — eine informierte Schätzung, die die Suche zum Ziel lenkt, ohne jede Sackgasse zu erkunden.
Dieser Artikel zeichnet die Idee nach: von Dijkstras blindem, aber optimalem Algorithmus (1959) über A*s informierte Suche (1968) bis zu AlphaGos neuronalen Netzwerk-Heuristiken (2016) — ein einzelnes Konzept, das klassische Informatik mit moderner KI verbindet.
Das Kostenproblem: Warum BFS an gewichteten Graphen scheitert
Im vorherigen Artikel hast du BFS und DFS kennengelernt — Algorithmen, die Graphen systematisch durchsuchen. BFS findet den kürzesten Weg gemessen an der Kantenzahl. Aber echte Straßen haben unterschiedliche Längen, unterschiedliche Geschwindigkeitsbegrenzungen und unterschiedliche Verkehrsaufkommen. BFS zählt nur Kanten, nicht Kosten.
Definition
Kostenfunktion
Analogie
Definition
Betrachte einen Stadtgraphen mit 6 Kreuzungen (A bis F), wobei jede Verbindung eine Fahrtzeit in Minuten hat. Die Verbindungen: A→B 5, B→C 8, C→F 7, B→E 12, E→F 10, A→D 25 und D→F 20 Minuten.
BFS wählt den Weg A→D→F (2 Kanten, 45 Minuten), weil er die wenigsten Kanten hat.
Dijkstra wählt A→B→C→F (3 Kanten, 20 Minuten), weil er die kumulierten Kosten verfolgt. Mehr Kanten, aber deutlich weniger Gesamtzeit.
Gleicher Graph, drastisch anderes Ergebnis. Kantenzählen versagt, sobald Kanten unterschiedliche Gewichte haben.
10 Städte (TSP)
181.440 Routen
Noch machbar für einen Computer
20 Städte (TSP)
6 ×10¹⁶ Routen
Jahrhunderte an Rechenzeit, wenn man alle durchprobiert
25 Städte (TSP)
3,1 ×10²³ Routen
Hunderte Millionen Jahre Rechenzeit, wenn man alle durchprobiert
Dijkstras Algorithmus löst dieses Problem. Er wurde 1956 von Edsger W. Dijkstra in einem Café in Amsterdam entworfen — in nur 20 Minuten, mit Mitte zwanzig — und 1959 veröffentlicht.
Dijkstra expandiert immer den bisher günstigsten nicht besuchten Knoten. Er verfolgt die kumulierten Kosten (g-Werte) vom Startknoten und garantiert bei nichtnegativen Kantengewichten den optimalen Pfad, sobald der Zielknoten als günstigster Knoten ausgewählt wird.
Aber Dijkstra hat eine entscheidende Einschränkung: Er sucht blind in alle Richtungen. Wie eine Wasserwelle, die sich von einem geworfenen Stein ausbreitet, flutet er den Graphen gleichmäßig — ohne zu wissen, wo das Ziel liegt.
Achtung
Irrtum: BFS findet den kürzesten Weg
BFS findet den kürzesten Weg nur in ungewichteten Graphen, in denen jede Kante gleich zählt. In gewichteten Graphen bedeutet weniger Kanten nicht weniger Kosten. Dijkstra korrigiert das, indem er kumulierte Kosten statt Kantenzahl verfolgt.
Heuristiken & A*: Suche mit Richtungssinn
Dijkstra findet den optimalen Pfad, aber er verschwendet enormen Aufwand, indem er in alle Richtungen sucht. Was wäre, wenn der Algorithmus wüsste, wo das Ziel liegt — und bevorzugt dorthin suchen würde?
Definition
Heuristik
Analogie
Definition
Definition
Zulässigkeit (Admissibility)
Analogie
Definition
A* bewertet jeden Knoten mit f(n) = g(n) + h(n): g(n) sind die tatsächlichen Kosten vom Start bis n, h(n) die geschätzten verbleibenden Kosten von n zum Ziel. A* expandiert immer den Knoten mit dem niedrigsten f(n)-Wert.
Wo die Kompass-Analogie bricht: Ein echter Kompass zeigt immer in eine feste Richtung. A*s Heuristik ändert ihren Wert an jedem Knoten. Außerdem zeigt der Kompass nur h(n) — die Analogie muss zusammen mit der Formel f(n) = g(n) + h(n) betrachtet werden, um diese Lücke zu schließen.
Merke
A* Schritt für Schritt
- 1. Wir starten bei Kreuzung A und schauen uns die Nachbarn an. Kreuzung B ist 5 Minuten entfernt (g=5). Die Luftlinie schätzt noch 14 Minuten zum Ziel (h=14), also f=19. Kreuzung D kostet 25 Minuten (g=25), Luftlinie 15 (h=15), also f=40.
- 2. B hat den kleinsten f-Wert (19), also gehen wir dorthin. Von B aus erreichen wir C: 5+8=13 Minuten bisher (g=13), Luftlinie zum Ziel nur noch 6 (h=6), also f=19. Außerdem erreichen wir E: 5+12=17 Minuten (g=17), Luftlinie 8 (h=8), also f=25.
- 3. C hat jetzt den besten f-Wert (19), also weiter. Von C erreichen wir F — das Ziel! Kosten: 13+7=20 Minuten. Da wir am Ziel sind, ist h=0.
- 4. Geschafft: Pfad A→B→C→F, 20 Minuten. A* hat nur 3 Kreuzungen geprüft — Dijkstra hätte 4 geprüft, weil er auch Kreuzung E (17 Minuten) vor dem Ziel (20 Minuten) geprüft hätte.
Expandiert 4 Knoten, sucht in alle Richtungen. Findet den optimalen Pfad A→B→C→F (20 min) — aber mit unnötigem Aufwand.
Expandiert 3 Knoten, durch Heuristik zum Ziel gelenkt. Findet den identischen optimalen Pfad A→B→C→F (20 min) — mit weniger Arbeit.
Merke
Historischer Kontext: A*
A* wurde 1968 von Peter Hart, Nils Nilsson und Bertram Raphael am Stanford Research Institute entwickelt, als Teil des Shakey-Roboterprojekts — eines der ersten autonomen mobilen Roboter. Veröffentlicht in den IEEE Transactions on Systems Science and Cybernetics, bewies A* erstmals, dass heuristische Suche optimale Ergebnisse garantieren kann.
Shakey: Der erste intelligente mobile Roboter
Die Geburt der autonomen Robotik durch Integration von Reasoning, Planning und physischer Aktion. Von 1966 bis 1972 entwickelte Charles Rosens Team am SRI International Shakey - den ersten mobilen Roboter, der über seine eigenen Handlungen reflektieren konnte. Der 2 Meter hohe Roboter kombinierte TV-Kamera, Sonar-Entfernungsmesser, Prozessoren und 'Katzen-Schnurrhaare' als Stoßdetektoren zu einem autonomen System. Shakeys bemerkenswerte Fähigkeiten umfassten Umgebungswahrnehmung, Schlussfolgerungen aus impliziten Fakten, Planerstellung und Fehlerkompensation - alles steuerbar durch natürliche englische Sprache. Das von der ARPA (heute DARPA) finanzierte Projekt vereinte erstmals logisches Reasoning mit physischer Aktion und legte Grundlagen für autonome Systeme. Shakeys Innovationen führten zum A*-Suchalgorithmus, zu Visibility-Graph-Methoden und zur einflussreichen rechnergestützten Variante der Hough-Transformation (Duda & Hart, SRI 1972). 1970 nannte Life Magazine Shakey die 'erste elektronische Person'.
Achtung
Irrtum: A* findet einen ungefähren Pfad
A* findet nicht nur eine Annäherung — mit einer zulässigen Heuristik findet A* den exakt gleichen optimalen Pfad wie Dijkstra. Der Unterschied liegt allein in der Effizienz: A* besucht weniger Knoten, um zum selben Ergebnis zu kommen.
Achtung
Irrtum: Jede Heuristik beschleunigt A*
Eine schlechte Heuristik kann A* sogar langsamer machen als Dijkstra — etwa wenn sie aufwendig zu berechnen oder nicht konsistent ist (siehe Deep Dive unten). Die Qualität der Heuristik ist entscheidend. Setzt man h(n) = 0 für alle Knoten, reduziert sich A* exakt zu Dijkstra — die Heuristik liefert dann keinerlei Richtungsinformation.
Zulässigkeit (h(n) ≤ h*(n)) reicht für Baumsuch-A* aus, um den optimalen Pfad zu garantieren. Graphensuch-A* — bei dem besuchte Knoten nicht erneut expandiert werden — benötigt eine stärkere Bedingung: Konsistenz (auch Monotonie genannt).
Eine Heuristik ist konsistent, wenn: h(n) ≤ c(n, n') + h(n') für jeden Knoten n und Nachfolger n', wobei c(n, n') die Kantenkosten von n nach n' sind. Intuitiv: die geschätzte Kostenabnahme zwischen zwei Knoten darf nicht größer sein als die tatsächlichen Kosten der Verbindungskante.
Konsistenz impliziert Zulässigkeit, aber nicht umgekehrt. In der Praxis sind die meisten natürlichen Heuristiken (wie die Luftlinienentfernung) konsistent. Diese Unterscheidung wird relevant bei der Implementierung von A* mit einer Closed-List.
Interaktiv: A* auf dem Gitter
Du hast gelernt, wie A* mit f(n) = g(n) + h(n) den optimalen Pfad findet. Jetzt kannst du den Algorithmus Schritt für Schritt auf einem 5×5-Gitter verfolgen: Beobachte, wie A* mit Manhattan-Distanz das Ziel ansteuert und Hindernisse umgeht.
Die Heuristik-Idee in moderner KI
A* funktioniert hervorragend auf Straßenkarten mit Tausenden von Knoten. Aber was ist mit Go, das etwa 2,08 × 10¹⁷⁰ legale Stellungen hat — mehr als es Atome im beobachtbaren Universum gibt (ca. 10⁸⁰)?
Merke
Das Heuristik-Spektrum
Von handgemacht bis gelernt: A* mit Luftlinienentfernung (exakte Garantie, Tausende Knoten) → Google Maps (handgemacht plus Echtzeitdaten, Milliarden Kanten, nahezu optimal) → AlphaGo (gelerntes neuronales Netzwerk, 10¹⁷⁰ Positionen, übermenschlich aber ohne Garantie) → LLMs (Wahrscheinlichkeitsverteilungen, keine Garantie, Halluzinationen möglich). Je größer der Suchraum, desto mehr verlagern sich Heuristiken von handgemacht zu gelernt.
AlphaGo besiegte 2016 Lee Sedol, Gewinner von 18 Welttiteln, 4:1. Es verwendet zwei neuronale Netzwerke als Heuristiken: ein Policy-Netzwerk (welcher Zug als nächstes?) und ein Value-Netzwerk (wie gut ist diese Stellung?). Diese sind gelernte Heuristiken — trainiert auf Millionen von Partien statt von Menschen erdacht.
A* ist ein Navigator mit perfekter Karte — garantiert kürzeste Route, präzise Entfernungen. AlphaGo ist ein erfahrener Taxifahrer, der die Stadt seit 30 Jahren kennt — keine Karte, aber ein untrügliches Gespür für die richtigen Straßen.
Die Taxifahrer-Analogie unterschätzt die Fehlerarten gelernter Heuristiken: Ein Taxifahrer, der falsch abbiegt, bemerkt es sofort und korrigiert. Ein neuronales Netz, das Go spielt, kann eine Stellung völlig falsch bewerten und in unsinnige Zugfolgen abdriften — ohne es zu merken. Gelernte Heuristiken können auf Weisen versagen, die handgemachte nicht können.
Die Heuristik-Idee taucht überall in der KI auf: heuristische Bewertungsfunktionen in Spielbäumen (Artikel zu MinMax & Pruning), Verlustfunktionen als Heuristiken für Modellqualität, Gradientenabstieg als heuristisch geleitete Suche durch den Parameterraum. Jedes KI-System, das einen zu großen Raum für Brute Force durchsucht, nutzt eine Form von Heuristik.
P ist die Klasse der Probleme, die effizient lösbar sind (in polynomieller Zeit). NP ist die Klasse der Probleme, deren Lösungen effizient überprüfbar sind. Die unbewiesene Vermutung P ≠ NP — eines der Clay-Millennium-Probleme (Preisgeld: 1 Million Dollar, ausgelobt am 24. Mai 2000) — besagt, dass manche Probleme effizient verifizierbar, aber nicht effizient lösbar sind.
TSP ist NP-schwer: Es existiert kein bekannter Algorithmus, der für alle Instanzen effizient die optimale Lösung findet. Falls P ≠ NP gilt, kann es einen solchen Algorithmus prinzipiell nicht geben — Heuristiken sind dann nicht nur praktisch nützlich, sondern fundamental notwendig.
Das motiviert das gesamte Heuristik-Paradigma: Wenn exakte Lösungen praktisch unerreichbar sind, werden gute Näherungen zum besten erreichbaren Ergebnis.
NP-schwer bedeutet NICHT unlösbar. Es bedeutet: kein bekannter effizienter exakter Algorithmus. Kleine Instanzen sind oft exakt lösbar, und gute Heuristiken finden für große Instanzen exzellente Näherungen.
Merke
Zusammenfassung
- Blinde Suche (BFS/DFS) ignoriert Kosten und explodiert kombinatorisch. Kostenfunktionen machen Graphen realistisch; Dijkstra findet den günstigsten Pfad — sucht aber in alle Richtungen.
- Eine Heuristik ist eine informierte Schätzung, kein Raten. A* kombiniert exakte bisherige Kosten g(n) mit geschätzten verbleibenden Kosten h(n). Wenn die Schätzung nie überschätzt (zulässig), findet A* garantiert den optimalen Pfad — bei guter Heuristik mit deutlich weniger Aufwand als Dijkstra.
- Die Heuristik-Idee skaliert von exakten Garantien (A* auf Straßenkarten) zu gelernten Approximationen (AlphaGo, neuronale Netze). Mit wachsenden Suchräumen weichen handgemachte Heuristiken gelernten — Garantien werden gegen praktische Effektivität eingetauscht.
Prüfen
Quiz: Heuristiken & Pfadsuche
Was stellt die Heuristik h(n) in A* dar?
Wähle eine Antwort
1. Was stellt die Heuristik h(n) in A* dar?
2. Nach dem Start bei A betrachtet A* die möglichen nächsten Schritte: B (g=5, f=19) und D (g=25, f=40). Welchen Knoten wählt A* als nächstes und warum?
3. Zwei Pfade von S nach G: S→A→G (Kosten 10) und S→B→G (Kosten 8). Die Heuristik gibt h(A)=3 und h(B)=12. Ist diese Heuristik zulässig?
4. Ein Entwickler verwendet A* mit einer Heuristik, die die verbleibenden Kosten durchgehend um 50% überschätzt. Was passiert im Vergleich zu Dijkstra?
Prüfen
Verständnischeck
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen