Dijkstra - Versionsgeschichte

Thoronador am 1. Mai 2008 um 15:44 Uhr

2008-05-01T15:44:13Z

Lyr: /* Erstellung des Graphen */ Fehler im Algorithmus

2006-04-09T04:46:46Z

‎Erstellung des Graphen: Fehler im Algorithmus

Lyr am 25. November 2005 um 01:28 Uhr

2005-11-25T01:28:11Z

Neue Seite

Dijkstra ist eine spezielle Form des Pathfinding. Hier geht es darum, für beliebig viele Agenten (oder "interessierte" computergesteuerte Einheiten) den kürzesten Weg zu einem bestimmten Ziel zu finden. Dieser Algorithmus ähnelt sehr dem Sprichwort: "Alle Wege führen nach Rom".

=Vorgehensweise=
Ausgehend von Rom (oder einem beliebigen anderen Zielort) erhält ein Graph in alle Richtungen die Kostenangaben (bzw. die Anzahl der Knoten die durchlaufen wurden). Dieser rekursive Vorgang wird so lange durchgeführt bis alle Knoten die Kosten zum Ziel besitzen. Wenn man nun von einem konkreten Knoten zu dem vorgegebenen Ziel möchte, so muss man sich nur den Nachbarknoten mit dem geringsten Wert raus suchen.

=Algorithmus=
==Erstellung des Graphen==
Dijkstra( Knoten Aktuell, Integer Bisherige_Kosten )
Wenn Bisherige_Kosten + Kosten( Aktuell, K ) < K.Kosten_zum_Ziel
K.Kosten_zum_Ziel = Bisherige_Kosten + Kosten( Aktuell, K )

Für K=alle noch nicht besuchten Nachbarknoten von Aktuell
Dijkstra( K, Bisherige_Kosten + Kosten( Aktuell, K ) )
Die Erstellung des Graphen benötigt eine Laufzeit von [[O-Notation|O]](n^2) wobei n die Anzahl der Knoten ist. Der Speicherbedarf für diesen Algorithmus (sowohl zur Generierung als auch die fertig generierte Tabelle) ist [[O-Notation|O]](n).

==Suchen eines Weges==
Zum suchen eines Weges von einem gegebenen Startpunkt zum Ziel muss man wie bereits erwähnt für jeden Knoten den Nachbarknoten suchen, welcher am nähesten beim Ziel liegt. Dies geschieht folgendermaßen:
Suche_Weg( Knoten Aktuell )
Wenn Aktuell.Kosten_zum_Ziel = 0
Ziel gefunden

Für K = Knoten mit den geringsten Kosten_zum_Ziel
Suche_Weg( K )
Dieser Algorithmus besitzt eine maximale Laufzeit von [[O-Notation|O]](t*v) wobei t die Tiefe (oder Entfernung) in Knoten des Zieles vom Startpunkt ist, und v der durchschnittliche Verzweigungsgrad des Graphen. Der Speicherbedarf für diesen Algorithmus ist im Idealfall [[O-Notation|O]](1) bzw. O(t) um den gesamten Pfad vom Start bis zum Ziel zu speichern, jedoch benötigt man natürlich die Tabelle von vorher welche einen Speicherbedarf von [[O-Notation|O]](n) besitzt.

@@ Zeile 1: / Zeile 1: @@
-Dijkstra ist eine spezielle Form des Pathfinding. Hier geht es darum, für beliebig viele Agenten (oder "interessierte" computergesteuerte Einheiten) den kürzesten Weg zu einem bestimmten Ziel zu finden. Dieser Algorithmus ähnelt sehr dem Sprichwort: "Alle Wege führen nach Rom".
+Der '''Dijkstra-Algorithmus''', benannt nach seinem Erfinder Edsger Wybe Dijkstra, ist eine spezielle Form des Pathfinding. Hier geht es darum, für beliebig viele Agenten (oder "interessierte" computergesteuerte Einheiten) den kürzesten Weg zu einem bestimmten Ziel zu finden. Dieser Algorithmus ähnelt sehr dem Sprichwort: "Alle Wege führen nach Rom".
 =Vorgehensweise=
-Ausgehend von Rom (oder einem beliebigen anderen Zielort) erhält ein Graph in alle Richtungen die Kostenangaben (bzw. die Anzahl der Knoten die durchlaufen wurden). Dieser rekursive Vorgang wird so lange durchgeführt bis alle Knoten die Kosten zum Ziel besitzen. Wenn man nun von einem konkreten Knoten zu dem vorgegebenen Ziel möchte, so muss man sich nur den Nachbarknoten mit dem geringsten Wert raus suchen.
+Ausgehend von Rom (oder einem beliebigen anderen Zielort) erhält ein Graph in alle Richtungen die Kostenangaben (bzw. die Anzahl der Knoten die durchlaufen wurden). Dieser rekursive Vorgang wird so lange durchgeführt, bis alle Knoten die Kosten zum Ziel besitzen. Wenn man nun von einem konkreten Knoten zu dem vorgegebenen Ziel möchte, so muss man sich nur den Nachbarknoten mit dem geringsten Wert raus suchen.
 =Algorithmus=
@@ Zeile 16: / Zeile 16: @@
 Die Abfrage "Knoten Aktuell bisher noch nicht besucht" kann entweder über einen eigenen boolean-Wert überprüft werden, oder aber durch einen speziellen Wert für die "Kosten_zum_Ziel" welcher maximial initialisiert wurde, also beispielsweise bei einem 16 Bit Integer ohne Vorzeichen mit FFFF Hex.
-Die Erstellung des Graphen benötigt eine Laufzeit von [[O-Notation|O]](n^2) wobei n die Anzahl der Knoten ist. Der Speicherbedarf für diesen Algorithmus (sowohl zur Generierung als auch die fertig generierte Tabelle) ist [[O-Notation|O]](n).
+Die Erstellung des Graphen benötigt eine Laufzeit von [[O-Notation|O]](n^2), wobei n die Anzahl der Knoten ist. Der Speicherbedarf für diesen Algorithmus (sowohl zur Generierung als auch die fertig generierte Tabelle) ist [[O-Notation|O]](n).
 ==Suchen eines Weges==
-Zum suchen eines Weges von einem gegebenen Startpunkt zum Ziel muss man wie bereits erwähnt für jeden Knoten den Nachbarknoten suchen, welcher am nähesten beim Ziel liegt. Dies geschieht folgendermaßen:
+Zum Suchen eines Weges von einem gegebenen Startpunkt zum Ziel muss man wie bereits erwähnt für jeden Knoten den Nachbarknoten suchen, welcher am nähesten beim Ziel liegt. Dies geschieht folgendermaßen:
   Suche_Weg( Knoten Aktuell )
     Wenn Aktuell.Kosten_zum_Ziel = 0
@@ Zeile 26: / Zeile 26: @@
     Für K = Knoten mit den geringsten Kosten_zum_Ziel
       Suche_Weg( K )
-Dieser Algorithmus besitzt eine maximale Laufzeit von [[O-Notation|O]](t*v) wobei t die Tiefe (oder Entfernung) in Knoten des Zieles vom Startpunkt ist, und v der durchschnittliche Verzweigungsgrad des Graphen. Der Speicherbedarf für diesen Algorithmus ist im Idealfall [[O-Notation|O]](1) bzw. O(t) um den gesamten Pfad vom Start bis zum Ziel zu speichern, jedoch benötigt man natürlich die Tabelle von vorher welche einen Speicherbedarf von [[O-Notation|O]](n) besitzt.
+Dieser Algorithmus besitzt eine maximale Laufzeit von [[O-Notation|O]](t*v), wobei t die Tiefe (oder Entfernung) in Knoten des Zieles vom Startpunkt ist, und v der durchschnittliche Verzweigungsgrad des Graphen. Der Speicherbedarf für diesen Algorithmus ist im Idealfall [[O-Notation|O]](1) bzw. O(t) um den gesamten Pfad vom Start bis zum Ziel zu speichern, jedoch benötigt man natürlich die Tabelle von vorher welche einen Speicherbedarf von [[O-Notation|O]](n) besitzt.

@@ Zeile 6: / Zeile 6: @@
 =Algorithmus=
 ==Erstellung des Graphen==
   Dijkstra( Knoten Aktuell, Integer Bisherige_Kosten )
     Wenn Bisherige_Kosten + Kosten( Aktuell, K ) < K.Kosten_zum_Ziel
       K.Kosten_zum_Ziel = Bisherige_Kosten + Kosten( Aktuell, K )
-    Für K=alle noch nicht besuchten Nachbarknoten von Aktuell
+    Wenn Knoten Aktuell bisher noch nicht besucht wurde
-     Dijkstra( K, Bisherige_Kosten + Kosten( Aktuell, K ) )
+     Für K=alle Nachbarknoten von Aktuell
 Die Erstellung des Graphen benötigt eine Laufzeit von [[O-Notation|O]](n^2) wobei n die Anzahl der Knoten ist. Der Speicherbedarf für diesen Algorithmus (sowohl zur Generierung als auch die fertig generierte Tabelle) ist [[O-Notation|O]](n).