Zurück zum Lernbereich

Heuristiken & Pfadsuche: Von Dijkstra zu A*

Wie A* funktioniert — und warum Dijkstra ohne Heuristik schnell langweilig wird.

  • Grundlagen
  • 10 min
  • Fortgeschritten

Einfache Sprache

Diese Vorschau ist in Einfacher Sprache. Das ganze Portal gibt es auch in Einfacher Sprache. Du kannst oben die Sprache wechseln. Oder nutze den Knopf unten. Unsere Texte in Einfacher Sprache entstehen KI-gestützt und werden redaktionell begleitet. Sie orientieren sich an den Grundprinzipien der Leichten Sprache, sind aber keine geprüfte Leichte Sprache: Eine Prüfgruppe von Menschen mit Lernschwierigkeiten prüft sie nicht.

Vorschau: Den besten Weg finden

Was ist Pfadsuche?

Ein Computer sucht den besten Weg von A nach B. Das heißt Pfadsuche. Pfadsuche bedeutet: Der Computer findet den besten Weg. So funktioniert auch ein GPS.

Dijkstra: Günstigster Weg

Dijkstra ist ein Algorithmus. Algorithmus bedeutet: eine Rechenanleitung. Dijkstra prüft alle Wege und wählt den günstigsten. Jede Verbindung hat einen Preis. Dijkstra sucht den kleinsten Gesamtpreis.

A*: Die schlaue Suche

A* ist schneller als Dijkstra. A* nutzt eine Heuristik. Heuristik bedeutet: eine kluge Schätzung. Die Schätzung zeigt, welcher Weg wahrscheinlich gut ist. So prüft A* weniger Wege.

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

Stell dir vor, du planst eine Autofahrt und jede Straße hat eine Mautgebühr. Die billigste Route ist nicht unbedingt die mit den wenigsten Abzweigungen — es ist die mit den niedrigsten Gesamtkosten. Eine Kostenfunktion weist jeder Straße (Kante) einen Preis (Gewicht) zu.

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

Stell dir vor, du wanderst durch einen unbekannten Wald auf einen Berggipfel zu, der am Horizont sichtbar ist. Ohne Kompass (= Dijkstra) würdest du systematisch jeden Weg in jede Richtung erkunden. Mit einem Kompass, der zum Gipfel zeigt (= Heuristik), bevorzugst du Wege in Richtung Ziel — während du trotzdem deine exakte Gehstrecke verfolgst.

Definition

Zulässigkeit (Admissibility)

Analogie

Der Kompass behauptet niemals, du seist näher am Gipfel, als du tatsächlich bist. Er kann die verbleibende Strecke unterschätzen (Berge haben Täler dazwischen), aber er überschätzt sie nie. Das ist Zulässigkeit: Die Schätzung ist immer optimistisch.

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. 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. 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. 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. 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.
Dijkstra

Expandiert 4 Knoten, sucht in alle Richtungen. Findet den optimalen Pfad A→B→C→F (20 min) — aber mit unnötigem Aufwand.

A*

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.

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.

Open Set
1
Closed Set
0

Drücke "Schritt", um A* auf dem Gitter zu starten.

Frei
Hindernis
Start
Ziel
Open Set
Ausgewertet
Aktuell
Pfad

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

  1. Blinde Suche (BFS/DFS) ignoriert Kosten und explodiert kombinatorisch. Kostenfunktionen machen Graphen realistisch; Dijkstra findet den günstigsten Pfad — sucht aber in alle Richtungen.
  2. 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.
  3. 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

Noch offen

Was stellt die Heuristik h(n) in A* dar?

Wähle eine Antwort

Auflösung: 1) B · 2) B · 3) B · 4) D

Prüfen

Verständnischeck

Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.

0 von 3 sitzen