Dijkstra: Unterschied zwischen den Versionen
Lyr (Diskussion | Beiträge) |
(kein Unterschied)
|
Version vom 25. November 2005, 02:28 Uhr
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".
Inhaltsverzeichnis
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(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(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(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(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(n) besitzt.