A-Stern-Algorithmus

Der A*-Algorithmus dient zur Berechnung eines kürzesten Pfades zwischen zwei Knoten s und e in einem zusammenhängenden kantengewichteten Graphen G.

Der Algorithmus verwendet dazu eine Schätzfunktion, die für jeden Knoten v eine untere Schranke für den noch zu erwartenden Abstand (im Sinne der Pfadlänge) von v nach e liefert. Durch die Verwendung dieser Funktion ergibt sich eine zielgerichtete Suche in Richtung auf den Endknoten. Zu beachten ist, dass es sich dabei um eine Heuristik handelt: Es werden zwar die "vielversprechendsten" Pfade zuerst untersucht, aber keine Lösungsmöglichkeit grundsätzlich ausgeschlossen.

Von entscheidender Bedeutung ist, dass die Schätzfunktion eine möglichst hohe, untere Schranke für die noch zu erwartende Pfadlänge liefern muss. Für die Suche in einer Landkarte (z.B. bei Routenplanern) erfüllt die Luftlinie diese Bedingung. Der Algorithmus sucht dann so, wie man es als Mensch auch tun würde: Wird z.B. eine Route von München nach Hamburg gesucht, macht es wenig Sinn, zuerst in Richtung Salzburg zu suchen, sondern man wird zuerst eine Strecke prüfen, die in Richtung Norden führt.

Der A*-Algorithmus ist vollständig, d.h. wenn ein Pfad zum Zielknoten existiert, so wird dieser auch gefunden. Außerdem ist er optimal, d.h. es gibt keinen kürzeren Pfad als den gefundenen. Zudem ist A* optimal effizient, d.h. jeder andere optimale und vollständige Algorithmus, der dieselbe Heuristik verwendet, muss mindestens so viele Knoten betrachten wie A*, um eine Lösung zu finden.

Algorithmus

Es wird eine Liste A von "aktuellen Knoten" verwaltet. Zu jedem Knoten wird sein Abstand von s auf dem kürzesten bisher gefundenen Pfad gespeichert. Soll außer der Länge des kürzesten Pfades auch der Pfad selbst gefunden werden, wird bei jedem Knoten in Schritt 4. auch sein Vorgänger gespeichert. Das Ergebnis kann dann in umgekehrter Reihenfolge (von e nach s) ermittelt werden.

• 1. Nimm den Startknoten s in A auf
• 2. Für jeden Knoten aus A: Berechne die Summe aus seinem Abstand von s und seiner Schätzfunktion und ermittle den Knoten v_min mit der geringsten Summe
• 3. Wenn
  

  dann wurde der kürzeste Weg gefunden

• 4. Ansonsten nimm die Nachfolger von v_min in A auf (v_min wird "aufgelöst") und gehe zu 2. Ist einer der Nachfolger bereits in A enthalten, nehme die Variante mit dem geringeren Abstand von s.

Zu beachten ist, dass die Suche nicht schon endet, wenn der Zielknoten e gefunden wird, sondern erst, wenn dieser als Kandidat für die "Auflösung" identifiziert wird.

Weblinks

• Skripte zur künstlichen Intelligenz und zum A*, TU Chemnitz