Dijkstra: Unterschied zwischen den Versionen
Lyr (Diskussion | Beiträge) K (→Erstellung des Graphen: Fehler im Algorithmus) |
K |
||
| 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= | =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= | =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 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== | ==Suchen eines Weges== | ||
| − | Zum | + | 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 ) | Suche_Weg( Knoten Aktuell ) | ||
Wenn Aktuell.Kosten_zum_Ziel = 0 | Wenn Aktuell.Kosten_zum_Ziel = 0 | ||
| Zeile 26: | Zeile 26: | ||
Für K = Knoten mit den geringsten Kosten_zum_Ziel | Für K = Knoten mit den geringsten Kosten_zum_Ziel | ||
Suche_Weg( K ) | 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. |
| + | |||
| + | [[Kategorie:Technik_oder_Algorithmus]] | ||
Aktuelle Version vom 1. Mai 2008, 16:44 Uhr
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".
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
Für diesen Algorithmus müssen die "Kosten_zum_Ziel"-Werte für alle Knoten mit dem maximalen Wert initialisiert werden (zB FFFF Hex für 16 Bit Integer ohne Vorzeichen).
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 )
Wenn Knoten Aktuell bisher noch nicht besucht wurde
Für K=alle Nachbarknoten von Aktuell
Dijkstra( K, Bisherige_Kosten + Kosten( Aktuell, K ) )
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(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.
