Einführung
Graph erstellen
Algorithmus ausführen
Beschreibung des Algorithmus
Forschungsaufgabe 1
Forschungsaufgabe 2
Weiteres

Wie komme ich am günstigsten von links nach rechts?

Eine informierte Suche nach dem kürzesten Weg

Du bist auf der Suche nach dem kürzesten Weg von Frankfurt nach München? Dabei könnte dir der Dijkstra-Algorithmus helfen. Allerdings weißt du schon, dass München südlich von Frankfurt liegt. Da der Dijkstra-Algorithmus seine Suche kreisförmig um den Start ausbreitet, könnte man die Suche beschleunigen, denn Städte im Norden möchtest du gar nicht erst betrachten.

Der A*-Algorithmus bietet sich für dieses Problem an. Er funktioniert ähnlich wie der Dijkstra-Algorithmus, sucht allerdings gezielter, da für einen Zielknoten, wie hier München, zunächst geschätzt wird, wie groß die Distanz sein wird.

Da der A*-Algorithmus sehr mit dem Dijkstra-Algorithmus verwandt ist, kannst du auch hier in einem Graphen, dessen Kanten mit den Distanzen zwischen verschiedenen Städten beschriftet sind, den kürzesten Weg zwischen zwei Städten ermitteln. Natürlich können die Kantenbeschriftungen auch beim A*-Algorithmus etwas anderes repräsentieren, wie zum Beispiel die Mautkosten auf den Autobahnen zwischen den Städten. Es ist jedoch wichtig, dass sie nicht negativ sind.

Hier wird der A*-Algorithmus vorgestellt, der günstigste Wege bei nicht-negativen Kosten zwischen zwei Knoten berechnet.

Was möchtest du zuerst tun?

SVG Download

Legende

	Knoten
	Kante mit Gewicht 50

Legende

Auf welchem Graph soll der Algorithmus ausgeführt werden?

Nimm ein fertiges Beispiel!

Ändere den Graphen nach deinen Vorstellungen:

Um einen Knoten zu erstellen, mache einen Doppelklick in das Zeichenfeld.
Um eine Kante zu erstellen, klicke zunächst auf den Ausgangsknoten und dann auf den Zielknoten.
Das Kantengewicht kann mit einem Doppelklick auf die Kante verändert werden.
Ein Rechtsklick löscht Kanten und Knoten.

Lade den veränderten Graphen herunter:

Download

Lade einen existierenden Graphen hoch:

Ein

trat auf beim Lesen der Datei:

Fehlerbeschreibung:

Was nun?

SVG Download

Legende

	Startknoten, von dem aus der günstigste Weg zum Zielknoten berechnet wird
	Zielknoten, zu dem vom Startknoten aus der günstigste Weg berechnet wird
	Knoten, dessen Bearbeitung abgeschlossen ist
	Knoten, der gerade bearbeitet wird
	Knoten, der sich in der Warteschlange befindet
	"Vorgängerkante", die der günstigste Weg zum Knoten benutzt

Legende

Status des Algorithmus

rewind Vorspulen

Erklärung
Pseudocode

BEGIN

d(v[1]) ← 0, parent(v[1]) ← v[1]

FOR i = 2,..,n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

h(v[i]) ← √(Σ(v[i].coord-ziel.coord)²)

queue.insert(v[1], 0)

WHILE queue ≠ ∅ DO

u = queue.extractMin()

IF u == ziel DO RETURN "Weg gefunden"

FOR ALL (u,w) ∈ E DO

dist ← d(u) + l(u,w)

IF w ∈ queue AND d(w) > dist DO

d(w) = dist, f = dist + h(u)

parent(w) = u

ELSE IF parent(w) == NULL THEN

d(w) = dist, f = dist + h(u)

parent(w) = u, queue.insert(w,f)

RETURN "Ziel nicht erreichbar"

END

Warteschlange:

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.

Wie komme ich am günstigsten von links nach rechts?

Idee des Algorithmus

Der A*-Algorithmus ist ein Algorithmus mit dem man den kürzesten Weg zwischen zwei Knoten bestimmen kann. Möchte man, wie beim Dijkstra-Algorithmus, alle kürzesten Wege von einem Startknoten zu allen anderen Knoten erhalten, so muss man den Algorithmus entsprechend oft ausführen.

Beim A*-Algorithmus spricht man auch von einem informierten Suchverfahren, da der Algorithmus im Gegensatz zum Dijkstra-Algorithmus nicht blind einfach die nächsten erreichbaren Knoten abarbeitet, sondern weitere Informationen hinzuzieht, um die Knoten auszuwählen, die wahrscheinlich schneller zum Ziel führen.

Als zusätzliche Information verwendet der A*-Algorithmus eine Schätzfunktion, das ist eine Art Daumenregel, die für jeden Knoten angibt, wie weit der Zielknoten ungefähr entfernt ist. Damit kann immer der Knoten als nächstes ausgewählt werden, der wahrscheinlich am schnellsten zum Zielknoten führt. Dadurch wird auch die Suche nach dem kürzesten Weg beschleunigt.

Funktionsweise des Algorithmus

Kante vor Update — Die Kante ist eine Abkürzung:
Wir wissen, dass es uns 20 kostet, um vom Startknoten zum linken Knoten zu gelangen. Der Weg vom linken zum rechten Knoten kostet 1.

Beim A*-Algorithmus befindet sich jeder Knoten in einem von drei Zuständen:

Der Knoten ist unbekannt: Er wurde noch nicht bearbeitet und somit ist auch noch kein Weg zu ihm bekannt.
Der Knoten befindet sich in der Warteschlange: Zu ihm wurde bereits ein Weg gefunden. Es könnte aber noch einen kürzeren Weg geben.
Der Knoten ist fertig abgearbeitet: Zu ihm wurde der kürzeste Weg vom Startknoten gefunden.

Bei der Ausführung des Algorithmus wird zunächst der Startknoten in die zuvor leere Warteschlange eingefügt. Jeder Knoten in dieser Warteschlange hat einen f-Wert, das ist die Summe aus der Distanz vom Startknoten zu diesem Knoten und der geschätzten Entfernung von diesem Knoten zum Zielknoten. Der Knoten, der gerade den geringesten f-Wert hat, steht vorne in der Warteschlange und wird als nächstes bearbeitet.

Nun werden solange Knoten mit dem momentan kleinsten f-Wert aus der Warteschlange entnommen bis man den Zielknoten entnimmt oder die Warteschlange leer ist. Ist der entnommene Knoten der Zielknoten, so ist der Algorithmus fertig, da der kürzeste Weg zu diesem Knoten gefunden wurde. Endet der Algorithmus jedoch, weil die Warteschlange leer ist, ohne dass der Zielknoten entommen wurde, so wurde kein Weg zum Zielknoten gefunden, da dieser vom Startknoten aus unerreichbar ist.

Wenn ein Knoten aus der Warteschlange entnommen wurde, ist er fertig abgearbeitet und als nächstes werden seine Nachbarknoten betrachtet. Für jeden der Nachbarknoten werden drei Fälle unterschieden:

Der Nachbarknoten ist bereits fertig abgearbeitet:
In diesem Fall passiert nichts weiter mit dem Knoten.
Der Nachbarknoten befindet sich bereits in der Warteschlange:
Ist der Weg über die neue Kante kürzer als der bisherige Weg, so wird der f-Wert aktualisiert.
Der Nachbarknoten war noch nicht in der Warteschlange:
Der f-Wert des Knotens wird ermittelt und der Knoten wird anhand des f-Werts in die Warteschlange eingereiht.

Für jeden Knoten, zu dem ein kürzester Weg gefunden wurde, kann dieser Weg wie unten beschrieben konstruiert werden.

Was ist eine zulässige Schätzfunktion?

Der f-Wert eines Knotens, der bestimmt, wie weit vorne der Knoten in der Warteschlange steht, ist die Summe der Distanz des Knotens zum Startknoten und der geschätzten Distanz des Knotens zum Zielknoten. Die Distanz zum Startknoten hängt von den tatsächlichen Kantenkosten ab. Für die geschätzte Distanz zum Zielknoten wird eine Schätzfunktion benötigt.

Als Schätzfunktion kann man zum Beispiel die Luftlinie von einem Knoten zum Zielknoten wählen. Mathematisch gesehen ist das dann der euklidische Abstand zwischen den beiden Knoten. Wenn die Koordinaten eines Knotens (x₁, y₁) sind und die Koordinaten des Zielknotens (x₂, y₂), dann ist der euklidische Abstand zwischen diesen beiden Knoten √((x₁-x₂)²+(y₁-y₂)²).

Der Algorithmus legt jedoch nicht fest, welche Schätzfunktion zu verwenden ist. Im Prinzip kann man diese frei wählen. Allerdings muss man darauf achten, dass die Schätzfunktion auch zulässig ist. Dies bedeutet, dass die Schätzfunktion niemals die Kosten für eine Strecke überschätzen darf. Wenn beispielsweise der Weg von Dorf A nach Dorf B 10 km lang ist. muss die geschätzte Distanz zwischen diesen beiden Dörfern kleiner als 10 km sein. Wenn diese Forderung nicht eingehalten würde, könnte es passieren, dass der Algorithmus keine korrekte Lösung findet, da der Zielknoten zu weit hinten in die Warteschlange eingereiht wird.

Graph mit eingezeichneten Abstandswerten — Der grüne Weg vom Startknoten ist der günstigste Weg. Er benutzt 3 Kanten.

Konstruktion des günstigsten Weges

Bei jeder Aktualisierung der Kosten speichert der Algorithmus den Knoten, der direkt vor ihm auf dem bisher günstigsten Weg zu ihm liegt, als Vorgängerknoten des Knotens. Oft wird dieser Knoten auch Vaterknoten genannt.

Am Ende des Algorithmus kann dann der günstigste Weg vom Start- zum Zielknoten konstruiert werden, indem man vom Zielknoten aus so lange über Vorgängerknoten läuft, bis man am Startknoten angekommen ist.

Wenn es von dem Startknoten aus zu einem Knoten keinen Weg gibt, so bleiben seine Kosten unendlich. Ebenso bleiben die Kosten der Knoten unendlich, die zwar erreichbar sind, aber auf dem kürzesten Weg vom Startknoten zum Zielknoten nicht besucht werden.

Was nun?

Einen Graph erstellen und den Algorithmus durchspielen

Sein Wissen an den Forschungsaufgaben testen

SVG Download

Legende

	Startknoten, von dem aus der günstigste Weg zum Zielknoten berechnet wird
	Zielknoten, zu dem vom Startknoten aus der günstigste Weg berechnet wird
	Knoten, dessen Bearbeitung abgeschlossen ist
	Knoten, der gerade bearbeitet wird
	Knoten, der sich in der Warteschlange befindet
	"Vorgängerkante", die der günstigste Weg zum Knoten benutzt

Legende

Wie verhält sich der Dijkstra-Algorithmus auf dem Gittergraphen?

rewind Zur nächsten Frage vorspulen

Erklärung
Pseudocode

BEGIN

d(v[1]) ← 0

FOR i = 2,..,n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

WHILE queue ≠ ∅ DO

u = queue.extractMin()

FOR ALL (u,w) ∈ E DO

dist ← d(u) + l(u,w)

IF w ∈ queue AND d(w) > dist DO

d(w) = dist, parent(w) = (u,w)

ELSE IF parent(w) == NULL THEN

d(w) = dist, parent(w) = (u,w)

queue.insert(w,dist)

END

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.

SVG Download

Legende

	Startknoten, von dem aus der günstigste Weg zum Zielknoten berechnet wird
	Zielknoten, zu dem vom Startknoten aus der günstigste Weg berechnet wird
	Knoten, dessen Bearbeitung abgeschlossen ist
	Knoten, der gerade bearbeitet wird
	Knoten, der sich in der Warteschlange befindet
	"Vorgängerkante", die der günstigste Weg zum Knoten benutzt

Legende

Wie verhält sich der A*-Algorithmus auf dem Gittergraphen?

rewind Zur nächsten Frage vorspulen

Erklärung
Pseudocode

BEGIN

d(v[1]) ← 0, parent(v[1]) ← v[1]

FOR i = 2,..,n DO

d(v[i]) ← ∞, parent(v[i]) ← NULL

h(v[i]) ← √(Σ(v[i].coord-ziel.coord)²)

WHILE queue ≠ ∅ DO

u = queue.extractMin()

IF u == ziel DO RETURN "Weg gefunden"

FOR ALL (u,w) ∈ E DO

dist ← d(u) + l(u,w)

IF w ∈ queue AND d(w) > dist DO

d(w) = dist, f = dist + h(u)

parent(w) = u

ELSE IF parent(w) == NULL THEN

d(w) = dist, f = dist + h(u)

parent(w) = u, queue.insert(w,f)

RETURN "Ziel nicht erreichbar"

END

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.

Wie sieht der (Pseudo-)Code des Algorithmus aus?

Eingabe: Gewichteter, ungerichteter oder gerichteter Graph G=(V,E) mit Gewichtsfunktion l,
         wobei alle Gewichte positiv sind, sowie ein Startknoten und ein Zielknoten.
Ausgabe: Kürzester Pfad zwischen Start- und Zielknoten


BEGIN
  d(start) ← 0, parent(start) ← start
  FOR i = 2,..,n DO
    d(v[i]) ← ∞, parent(v[i]) ← NULL
    h(v[i]) ← √((v[i].x-ziel.x)² + (v[i].y-ziel.y)²)
  queue.insert(start,0)
  WHILE queue ≠ ∅ DO
    u = queue.extractMin()
    IF u == ziel DO 
      getPath()
      RETURN "Weg gefunden"
    FOR ALL (u,w) ∈ E DO
      dist ← d(u) + l(u,w)
     IF w ∈ queue AND d(w) > dist DO
       d(w) = dist, f = dist + h(u)
       parent(w) = u
     ELSE IF parent(w) == NULL THEN
       d(w) = dist, f = dist + h(u)
       parent(w) = u, queue.insert(w,f)
  RETURN "Ziel nicht erreichbar"
END


getPath():
BEGIN
 node ← ziel
 WHILE parent(node) != start DO
   path.add(node)
   node ← parent(node)
 path.add(start)
 invert(path)
 RETURN path
END

Da der kürzeste Pfad rückwärts, also vom Zielknoten ausgehend, bestimmt wird, muss noch eine Invertierungsfunktion aufgerufen werden, die die Reihenfolge der Knoten umdreht. Dadurch erhält man den Pfad in der richtigen Anordnung vom Startknoten ausgehend bis zum Zielknoten.

Wie schnell ist der Algorithmus?

Geschwindigkeit von Algorithmen

Die Geschwindigkeit von Algorithmen wird üblicherweise in der Anzahl an Einzelschritten gemessen, die der Algorithmus bei der Ausführung benötigt.

Einzelschritte sind beispielsweise:

Zuweisungen – Weise Knoten 1 den Wert 20 zu.
Vergleiche – Ist 20 größer als 23?
Vergleich und Zuweisung – Falls 20 größer als 15 ist, setze Variable n auf 20.
Einfache Arithmetische Operationen – Was ist 5 + 5 ?

Da es sehr schwierig sein kann, diese Einzelschritte exakt zu zählen, möchte man nur die ungefähre Größenordnung der Anzahl Schritte wissen. Man spricht auch von der Laufzeit des Algorithmus. Meistens ist es besonders interessant, zu wissen, wie die Geschwindigkeit des Algorithmus von der Größe der Eingabe (hier: Anzahl Kanten und Knoten im Graph) abhängt.

Laufzeit des A*-Algorithmus

Wenn man die Laufzeit eines Algorithmus bestimmt, betrachtet man in der Regel den schlechtesten Fall der Ausführung. Da die Stärke des A*-Algorithmus in der Schätzfunktion liegt, ist der schlechteste Fall der, wenn die Schätzfunktion keine Vorteile bringt. Darum ist die Laufzeit des Algorithmus im Grunde die gleiche wie beim Dijkstra-Algorithmus, bei dem man keine Schätzfunktion hat:

Nehmen wir an, dass der A*-Algorithmus auf einem Graph mit n Knoten und m Kanten ausgeführt wird.

Da jeder Knoten des Graphen betrachtet wird, brauchen wir mindestens n Schritte.

Um einen Knoten zu behandeln, muss er zuerst aus der Warteschlange entnommen werden. Da wir jedoch immer nur den Knoten, der momentan die geringste Distanz zum Startknoten hat, entnehmen, kann man sich die Warteliste so vorstellen, dass aus allen n Knoten derjenige mit der geringsten Distanz gesucht wird. Um die Knoten auszuwählen braucht der Algorithmus also n · n Einzelschritte.

Um neue Knoten in die Warteschlange einzufügen, werden die Nachbarknoten der ausgehenden Kanten dieses Knotens betrachtet und anhand des Gewichts entschieden, ob der Nachbarknoten in die Warteschlange eingereiht wird oder nicht. Somit werden alle erreichbaren Kanten betrachtet, was bedeutet, dass der Algortihmus weitere m Einzelschritte benötigt.

Insgesamt liegt die Laufzeit des Algortihmus also in der Größenordnung m+n², wenn man die Warteschlange als Liste von Knoten betrachtet.

Es ist auch möglich diese Laufzeit weiter zu verbessern, sodass sie nur noch in der Größenordnung m+n· log(n) liegt. Dazu muss man jedoch für die Warteschlange eine andere Datenstruktur, nämlich einen Heap verwenden.

Was ist der Unterschied zum Dijkstra-Algorithmus?

Der Dijkstra-Algorithmus und der A*-Algorithmus ähneln sich stark. Du hast auch bereits gesehen, dass die Laufzeit des A*-Algorithmus im schlechtesten Fall im Grunde die gleiche ist wie beim Dijkstra-Algorithmus.

Wann sollte man den A*-Algorithmus verwenden?

Die Laufzeit gibt lediglich eine Größenordnung für allgemeine Fälle an. Der A*-Algorithmus nutzt jedoch eine Schätzfunktion, die man, sofern sie zulässig ist, selbst auswählen kann. In der Forschungsaufgabe, in der der Dijkstra-Algorithmus mit dem A*-Algorithmus verglichen wurde, konntest du sehen, dass der A*-Algorithmus mit einer geeigneten Schätzfunktion weniger Knoten besuchen muss, bis der Zielknoten gefunden wird.

Da weniger Knoten zu besuchen auch gleichzeitig bedeutet, dass die Laufzeit des Algorithmus schneller ist, sollte man, wenn es eine geeignete Schätzfunktion gibt, den A*-Algorithmus wählen.

Die Schätzfunktion macht auch den eigentlichen Unterschied zwischen den beiden Algorithmen aus. Beim Dijkstra-Algorithmus wird immer der Knoten aus der Warteschlange entnommen, der die nächst kleinste Distanz zum Startknoten hat. Beim A*-Algorithmus wird jedoch der Knoten entnommen, bei dem die Distanz zum Startknoten zusammen mit der geschätzten Distanz zum Zielknoten am geringsten ist. Diese geschätzte Distanz entspricht der Schätzfunktion

Wann sollte man den Dijkstra-Algorithmus verwenden?

Man kann den Dijkstra-Algorithmus als Spezialfall des A*-Algorithmus betrachten. In dem Fall ist die Schätzfunktion eine konstante Funktion, die für jeden Knoten, den Wert 0 hat. Beim A*-Algorithmus ist für die Warteschlange die Summe aus Distanz zum Startknoten und der Schätzwert zum Zielknoten entscheidend. Wenn der letzte Wert auf null gesetzt wurde, betrachtet man nur noch die Distanz zum Startknoten. Dadurch verhält sich der Algorithmus genau so wie beim Dijkstra-Algorithmus.

Der A*-Algorithmus ist also nur besser, wenn man ihn mit einer guten Schätzfunktion verwendet. Es gibt aber auch Anwendungen, bei denen man kürzeste Wege finden möchte und gar kein genaues Ziel vor Augen hat oder man weiß nicht genau, wo sich dieses Ziel befindet. Wenn man beispielsweise mit dem Auto unterwegs ist und die nächste Tankstelle finden möchte, weiß man zu Beginn der Suche noch nicht, wo diese liegt. In solchen Fällen ist der Dijkstra-Algorithmus eine bessere Wahl.

Wo finde ich noch mehr Informationen zu Graphalgorithmen?

Weitere Graphalgorithmen werden auf der Webseite des Lehrstuhls M9 der TU München erklärt.

Außerdem gibt es ein interessantes Buch zu kürzesten Wegen: Das Geheimnis des kürzesten Weges

Ein Mathematikstudium an der TU München beantwortet alle Fragen zur Graphentheorie (falls eine Lösung bekannt ist).

Ein letzter Hinweis zum Ziel und Inhalt dieser Seite und zu Zitationen

Der Lehrstuhl M9 der TU München beschäftigt sich mit diskreter Mathematik, angewandter Geometrie und der mathematischen Optimierung von angewandten Problemen. Die hier dargestellten Algorithmen sind sehr grundlegende Beispiele für Verfahren der diskreten Mathematik (die tägliche Forschung des Lehrstuhls geht weit darüber hinaus). Die vorliegenden Seiten sollen SchülerInnen und Studierenden dabei helfen, diese auch im realen Leben sehr wichtigen Verfahren (besser) zu verstehen und durch Ausprobieren zu durchdringen. Aus diesem Grund konzentriert sich die Darstellung bewusst auf die Ideen der Algorithmen, und präsentiert diese oftmals unter weitestgehendem Verzicht auf mathematische Notation.

Bitte beachten Sie, dass diese Seiten im Rahmen von studentischen Arbeiten unter Betreuung des Lehrstuhls M9 erstellt wurden. Den dabei entstandenen Code und die zugehörige Darstellung können wir nur punktuell überprüfen, und können deshalb keine Garantie für die vollständige Korrektheit der Seiten und der implementierten Algorithmen übernehmen.

Selbstverständlich freuen wir uns über jegliches (auch kritisches) Feedback bezüglich der Anwendungen sowie eventuellen Ungenauigkeiten und Fehlern der Darstellung und der Algorithmen. Bitte nutzen Sie hierzu den Anregungen-Link, welcher auch rechts in der Fußleiste zu finden ist.

Um diese Seite zu zitieren, nutze bitte die folgenden Angaben:

Titel: Der A* - Algorithmus
Autoren: Melanie Herzog, Wolfgang F. Riedl, Lisa Velden; Technische Universität München
Link: https://www-m9.ma.tum.de/graph-algorithms/spp-a-star