A-Stern

Der A-Stern Algorithmus besitzt unter den Pathfinding-begeisterten nahezu den Status des heiligen Grales, und dies nicht zu unrecht. Der A-Stern Algorithmus liefert unter gewissen Voraussetzungen den optimalen Weg und dies noch dazu meistens in einem sehr akzeptablen Zeitraum.

Vorgehensweise

Ähnlich zur Breitensuche wird hier immer der erahnte kürzeste Weg bevorzugt. Zum "erahnen" eines Weges wird eine Heuristik benötigt, also ein Wert welcher Angibt wie weit es ungefähr noch bis zum Ziel sein wird. Die Breitensuche wird nun einfach um diese Heuristik erweitert und dadurch wird der nächste zu überprüfende Knoten bestimmt.

Algorithmus

Suche_Weg( Knoten Ziel, Knoten Start )
  Kosten_Heap KHeap
  KHeap.Add( Min_Kosten( Start, Ziel ) )

  Solange Ziel nicht gefunden
    K = Knoten mit minimalen Kosten aus KHeap

    Wenn K = Ziel
      Ziel gefunden

    Für K' = alle (nicht besuchten) Nachbarknoten von K
      KHeap.Add( Kosten( Start, K' ) + Min_Kosten( K', Ziel ), K' )

Durch die minimalen Kosten von K zum Ziel setzen wir voraus, das wir eine derartige Funktion besitzen. Und es lässt sich recht einfach durch Worte beweisen, dass dieser Algorithmus wirklich den optimalen Weg findet:

Dieser Algorithmus erweitert den Knoten mit den minimalen bisherigen Kosten + den minimal zu erwartenden Kosten.
Wenn die minimal zu erwartenden Kosten kleiner (oder gleich) den tatsächlichen Kosten ab dem Punkt wo er
sich befindet sind, so können die tatsächlichen Kosten für den ersten gefundenen Weg niemals höher sein als
die Kosten für einen bereits durchsuchten Weg + dessen minimaler Kosten und somit auch niemals höher als die
Kosten für einen bereits durchsuchten Weg + dessen tatsächliche Kosten zum Ziel.

Der Algorithmus besitzt jedoch immer noch eine maximale Laufzeit von O(n) jedoch kann man dies wiederum umformen in O(t^v) wobei t die Tiefe des Zieles ist und v der (durchschnittliche) Verzweigungsgrad des Baumes, bzw. des Graphen ohne wiederholte Knoten ist. Jedoch für die durchschnittliche Laufzeit kann man hier v auch als Verzweigungsgrad des Baumes in die "ungefähre" Richtung des Zieles sehen, und dieser ist meistens um einiges geringer als der tatsächliche Verzweigungsgrad. Der maximale Speicherbedarf ist jedoch (leider) wiederum O(t^v).

Wenn jedoch der Wert der durch Min_Kosten berechnet wird die minimalen Kosten überschreiten kann, so liefert dieser Algorithmus nicht mehr zwingendermaßen den minimalen Weg, denn dann wird obiger (textuelle) Beweis nichtig. Aufzupassen ist somit auf schnellere Fortbewegungsmöglichkeiten wie beispielsweise:

• Die Heuristik von A-Stern wird mit den Daten "zu Fuß gehen" gefüttert, es gibt jedoch auch eine Zugverbindung
• Es gibt einen Teleporter welcher ohne Zeitverlust eine Passage von A nach B öffnet.

Die minimalen Kosten müssen somit mit dem schnellsten Transportmittel über Luftlinie berechnet werden.

Die Qualität des A-Stern-Algorithmus beruht somit auf der Qualität der Heuristik. Sowohl darauf, dass die Heuristik für die minimalen Kosten niemals höher wird als die tatsächlichen Kosten, als auch darauf, dass die tatsächlichen Kosten niemals allzu viel höher werden als die minimalen Kosten. Wenn man für diese Heuristik immer den Wert 0 verwendet, so entspricht A-Stern einer Breitensuche.

A-Stern mit Kosten

Wie am Ende des vorigen Absatzes bereits klar geworden sein sollte, benötigt A-Stern Kosten (vor allem minimale Kosten), ansonsten degeneriert er zu einer Breitensuche.