Heuristiken & Pfadsuche: Von Dijkstra zu A*

Dein GPS findet die schnellste Route durch Millionen von Kreuzungen in Millisekunden. Es prüft nicht jede mögliche Route — bei nur 20 Stopps gibt 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 Sackgassen 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.

Betrachte einen Stadtgraphen mit 6 Kreuzungen (A bis F), wobei jede Verbindung eine Fahrtzeit in Minuten hat.

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.

Dijkstras Algorithmus löst dieses Problem. Er wurde 1956 von Edsger W. Dijkstra in einem Café in Amsterdam entworfen — in nur 20 Minuten, im Alter von 26 Jahren — 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 den optimalen Pfad, sobald der Zielknoten erreicht 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.

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?

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.

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⁸⁰)?

AlphaGo besiegte 2016 den Weltmeister Lee Sedol 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: Alpha-Beta-Pruning in Spielbäumen (nächster Artikel), 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.