Zum Hauptinhalt springen
24ef

A-Stern

Der AA^\star-Algorithmus[1] (im folgenden AA^\star genannt) wird verwendet, um in einem Baum oder allgemein in einem Graphen den kürzesten Pfad zwischen zwei Knoten zu finden. Um AA^\star anwenden zu können, müssen die Kanten mit Kosten versehen sein. Gesucht ist nun der kürzeste (bzw. billigste) Pfad zwischen zwei Knoten.

Bei der Breitensuche wird keine «intelligente» Auswahl der Knoten in der Open-List getroffen, die Knoten werden in willkürlicher Reihenfolge verarbeitet. Der AA^\star ist eine Verfeinerung dieser Verfahren, wobei folgendermassen immer der vielversprechendste Knoten weiterverarbeitet wird. Es wird abgeschätzt, wie «gut» ein Knoten ist, indem eine Bewertungsfunktion berechnet wird. Die Kosten eines Knotens NN beinhalten zwei Beiträge: einerseits die Kosten vom Startknoten bis zu NN (wie bei Dijkstra) und andererseits die geschätzten Kosten von NN bis zum Zielknoten. Diese Bewertungsfunktion f(N)f(N) für einen Knoten NN wird also folgendermassen definiert:

A-Stern

f(N)=g(N)+h(N)f(N) = g(N) + h(N)

wobei g(N)g(N) die Kosten des Pfades vom Startknoten zu NN darstellt und h(N)h(N) die geschätzten Kosten eines optimalen Pfades von NN zum Zielknoten darstellt.

Bei der Schätzung muss gelten:

h(N)h(N)h(N) \geq h^*(N)

wobei h(N)h^\star(N) die tiefstmöglichen Kosten für die Verbindung von NN zum Zielknoten sind (dieser Pfad muss nicht zwingen über den vorhanden Graphen verlaufen. A* könnte andernfalls falsche Resultate liefern, wenn plötzlich eine neue, direktere Verbindung von N zum Ziel gebaut wird. Deshalb ist die Luftlinie eine gute heuristik - schneller geht es mit herkömmlichen Gesetzen der Physik nicht).

Die Funktion hh ist eine sog. Heuristik, also eine Abschätzung des wahren Werts. So kann die Suche nach dem optimalen Pfad oft wesentlich beschleunigt werden, was beim AA^\star ausgenutzt wird. Man kann zeigen, dass der immer den kürzesten Weg findet, wenn es einen gibt.

Beispiel

Gesucht ist der schnellste Weg von Würzburg nach Saarbrücken. Durch Abstraktion der Karte wurde der folgende gewichtete Graphen erzeugt. Zusätzlich kennt man für jeden Knoten eine Heuristik, nämlich die Distanz der Luftlinie nach Würzburg:

Saarbrücken

Start beim Ziel. Für alle anliegenden Knoten f(Knoten)=g(Knoten)+h(Knoten)f(Knoten) = g(Knoten) + h(Knoten) berechnet, also "Distanz vom Ziel bis zum Knoten" + "Luftlinie vom Knoten bis zum Start".

Kaiserlautern

f=70+158=228f = 70 + 158 = 228

Karlsruhe

f=145+140=285f = 145 + 140 = 285

  • Orientiere die Kanten in Richtung des Verbindungspfades

  • Markiere Saarbrucken als besucht

  • Besuche den Knoten mit dem kleinsten ff-Wert: Kaiserslautern

Aufgabe 1: Vergleich Dijkstra und A*-Algorithmus

Berechnen Sie für das Folgende Strassennetz den kürzesten Weg von nach München nach Frankfurt mit dem A*-Algorithmus. Die Entfernungen zwischen den Städten sind in der Abbildung angegeben.

Als Heuristik sollen folgende Luftlinien-Entfernungen verwendet werden:

Augsburg <--> München: 43 km
Erfurt <--> München: 342 km
Frankfurt <--> München: 353 km
Karlsruhe <--> München: 260 km
Kassel <--> München: 446 km
Mannheim <--> München: 311 km
München <--> München: 0 km
Nürnberg <--> München: 151 km
Würzburg <--> München: 229 km
SSR

Vergleich der Algorithmen

Die drei Algorithmen Breitensuche, Dijkstra und A-Stern-Algorithmus unterscheiden sich in ihrer Vorgehensweise und in ihrer Effizienz. Die folgende Tabelle gibt einen Überblick:

Aufgabe 2

Auf der verlinkten Seite können Breitensuche, Dijkstra und A-Stern miteinander vergleichen werden. Testen Sie die Seite aus und beantworten Sie folgende Fragen:

  • Was ist «Breadth First»?

  • Was ist «Depth First»?

  • Wofür stehen die Farben wenn man bei Terrain den Eintrag Simplex Terrain wählt. Welchen Einfluss haben diese auf den A-Stern-Algorithmus?

⭐ Zusatzaufgabe 3

Der A-Stern-Algorithmus kommt auch in Computer-Spielen zu Einsatz: Lesen Sie den folgenden Beitrag durch und testen Sie die tollen (und teilweise interaktiven) Visualisierungen: