Routenoptimierung / Kostenbasierte Suche / A-Stern Algorithmus

Zurück zum Inhaltsverzeichnis

A-Stern Algorithmus

Der A* Algorithmus dient zur Ermittlung des kostengünstigsten Pfades zwischen einem Start- und einem Zielknoten innerhalb eines Suchbaums. Er ist ein informiertes und erschöpfendes Verfahren zugleich, aber nur auf Suchprobleme anwendbar, bei denen bereits während der Suche plausible Annahmen darüber getroffen werden können, wie weit man vom Erreichen des Lösungszustandes noch entfernt ist. Beim Expandieren der Knoten innerhalb eines Suchbaumes werden die Kosten aller neuen Knoten mittels der Funktion

K = K_b + H

berechnet. K steht für die zu berechnenden Kosten, K_b für die Summe der Kosten, die bisher aufgelaufen sind, um den jetzigen Knoten zu erreichen und H für eine heuristische Schätzfunktion. Sie gibt den Wert der minimalen Kosten vom aktuellen Knoten zum Zielknoten an. Wichtig hierbei ist, daß die Schätzfunktion die untere Schranke bildet, also wirklich die theoretisch minimalen Kosten zur Erreichung des Zielknotens verwendet, da die Suche sonst in die Irre geleitet werden kann.

Das eigentliche Vorgehen des Algorithmus ist einfach: Bei jedem Schritt wird derjenige Knoten expandiert, dessen Kosten K am geringsten sind. Soll neben den Kosten des günstigsten Pfades auch der Pfad selbst gespeichert werden, so ist neben den Kosten auch der Vorgänger eines jeden Knotens zu speichern. Die programmtechnische Umsetzung verläuft nach folgendem Schema^,:

Ein einfaches Beispiel zur Ermittlung des kürzesten Weges soll das Vorgehen erläutern. Untenstehende Abbildung zeigt das Problem. Gesucht wird der kürzeste Weg von rot nach grün (a). Zuerst wird der Startknoten (rot) und der Zielknoten (grün) definiert. Als Knoten werden turtles eingesetzt, deren Farbe anzeigt, zu welcher Liste (OPEN oder CLOSED) sie gehören. Grau zeigt an, daß sich ein Knoten in der OPEN Liste befindet, rot, daß er sich in der CLOSED Liste befindet. Nun wird oben beschriebenes Schema angewandt. Bei der Initialisierung wird der Startknoten der OPEN Liste hinzugefügt und er expandiert Nachfolgeknoten in alle Möglichen Richtungen (b). Alle Nachfolgeknoten werden auf den PARENT-Knoten ausgerichtet. Die Kosten der Expansion betragen für die Knoten in der von-Neuman-Nachbarschaft eins, für die in diagonaler Richtung expandierten Knoten Wurzel zwei. Nun wird der Wert für die heuristische Schätzfunktion H ermittelt. Als Schätzfunktion dient die euklidische Distanz zum Zielknoten. Sie bildet garantiert eine unter Schranke, das heißt, daß kein kürzerer Weg möglich ist. Im Anschluß werden für jeden der Nachfolgeknoten die Gesamtkosten K nach oben genannter Formel berechnet. Der Knoten mit den geringsten Kosten ist in diesem Fall der direkt rechts des Starknotens. Deshalb expandiert er als nächstes (c). Da er selbst keine Verbesserung mehr erfahren kann, wird er auf die CLOSED Liste gesetzt und ändert seine Farbe nach rot. Auf den patches, auf denen sich nun zwei turtles befinden, kommt es zu einem Vergeich zwischen den Gesamtkosten. Diejenige turtle, die die geringeren Kosten akkumuliert hat, bleibt bestehen, die andere wird verworfen Dieser Vorgang wiederholt sich, bis der Zielknoten erreicht ist (h). Bei diesem Beispiel werden Knoten, die sich auf einem blauen patch befinden, sofort verworfen. Deshalb ist ein Überwinden der blauen Linie nicht möglich. In dem Fall, daß zwei Knoten gemeinsam die geringsten Kosten akkumuliert haben, wird zufällig einer dieser Knoten ausgewählt (d und e). Ab dem Moment, in dem der Wert H eines Knotens viel geringer ist als bei den anderen Knoten, sind seine Gesamtkosten ebenfalls viel geringer. Es expandieren nur noch die Knoten, die direkt auf dem Weg zum Zielknoten liegen (e bis h), es sei denn, daß sie durch ihre stetige Expansion höhere Kosten akkumulieren, als weiter von Zielknoten entfernte Knoten. Ist der Zielknoten erreicht, läßt sich die optimale Route durch Zurückverfolgen der turtles in entgegengesetzter Pfeilrichtung ermitteln.

Das Verfahren ist nicht zu Verwechseln mit dem gängigen GIS-Ansatz zur Ermittlung eines kürzesten Weges in einer Rasteroberfläche (wie zum Beispiel beschrieben bei Bernhardsen 2001, S. 291). Im Gegensatz zu dieser Methode bleibt der A* Algorithmus nicht in lokalen Optima stecken.