Logo Kürzeste Wege in Graphen: Der A*-Algorithmus Technische Universität München
Einfacher Graph mit 4 Knoten.

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 Knoten
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 Startknoten, von dem aus der günstigste Weg zum Zielknoten berechnet wird
Zielknoten Zielknoten, zu dem vom Startknoten aus der günstigste Weg berechnet wird
Abgeschlossener Knoten Knoten, dessen Bearbeitung abgeschlossen ist
Aktueller Knoten Knoten, der gerade bearbeitet wird
Knoten in Warteschlange Knoten, der sich in der Warteschlange befindet
Knoten "Vorgängerkante", die der günstigste Weg zum Knoten benutzt

Legende

Status des Algorithmus

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)2)

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:

Your browser does not support HTML5 Canvas. Please use a modern browser, i.e.Mozilla Firefox

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 Startknoten, von dem aus der günstigste Weg zum Zielknoten berechnet wird
Zielknoten Zielknoten, zu dem vom Startknoten aus der günstigste Weg berechnet wird
Abgeschlossener Knoten Knoten, dessen Bearbeitung abgeschlossen ist
Aktueller Knoten Knoten, der gerade bearbeitet wird
Knoten in Warteschlange Knoten, der sich in der Warteschlange befindet
Knoten "Vorgängerkante", die der günstigste Weg zum Knoten benutzt

Legende

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

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 Startknoten, von dem aus der günstigste Weg zum Zielknoten berechnet wird
Zielknoten Zielknoten, zu dem vom Startknoten aus der günstigste Weg berechnet wird
Abgeschlossener Knoten Knoten, dessen Bearbeitung abgeschlossen ist
Aktueller Knoten Knoten, der gerade bearbeitet wird
Knoten in Warteschlange Knoten, der sich in der Warteschlange befindet
Knoten "Vorgängerkante", die der günstigste Weg zum Knoten benutzt

Legende

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

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)2)

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.