dennismijo - Do 01.01.09 17:19
Titel: Kürzester Weg algorithmus

---

Hallo!
Ich stehe gerade vor folgendem Problem:

Aufgabe ist es, den kürzesten Weg zwischen zwei Punkten zu finden.

Bild:
http://img60.imageshack.us/my.php?image=algorithgr3.png

Angenommen ich möchte von Punkt [0, 0] zu Punkt [3, 3]. Wie könnte ich vor gehen?
Schwarze Felder sind "Tote Felder" und dürfen nicht berührt werden.
Jeder Punkt (nicht wenn sie am Rand liegen) hat 6 Verbindungen zum nächsten. (Unten, oben, links, rechts, unten rechts, oben links).Wie könnte man die einzelnen Verbindungen Gewichten?

Inwiefern ist mir der Dijskra-Algorithmus eine Hilfe und wie könnte man diesen ggf. anwenden?

Hat jemand von Euch irgendwelche Vorschläge?Pseudocodes o.ä?

Vielen Dank, Frohes Neues!

Lg Dennis

jaenicke - Do 01.01.09 17:26

---

Da du hier keine Kantengewichte hast, könntest du einfach eine Breitensuche durchführen. Dijkstra und Bellman-Ford braucht man eher bei gewichteten Graphen.
http://de.wikipedia.org/wiki/Breitensuche

dennismijo - Do 01.01.09 17:41

---

Ah vielen Dank!
Das war wohl der entscheidene Hinweis. :)

Kha - Do 01.01.09 23:05

---

jaenicke hat folgendes geschrieben :

Da du hier keine Kantengewichte hast, könntest du einfach eine Breitensuche durchführen.

Das dürfte von der Laufzeit her aber nur bei allerkleinsten Karten akzeptabel sein.

Solche Karten mit Hindernissen, wie sie auch oft in PC-Spielen vorkommen, sind das Paradebeispiel für A* [http://de.wikipedia.org/wiki/A*-Algorithmus], einen heuristischen Verwandten des Dijkstra.

jaenicke - Do 01.01.09 23:35

---

Dazu gibt es auch eine gute Beschreibung und ein Beispiel in Delphi in der DP von Daniel. Moment... genau, hier:
http://www.delphipraxis.net/post565850.html
Den Beitrag fand ich recht gut verständlich. (Besser als das was ich im Studium dazu gelesen hatte. :D)

Ich war aber davon ausgegangen, dass es eher eine Übungsaufgabe war, bei der die Optimierung nicht ganz so wichtig ist, und einfacher ist die Breitensuche. ;-)

dennismijo - So 04.01.09 02:38

---

Vielen Dank, für eure Antworten.
Die A* vorgehensweise finde ich sehr interessant.

Ein Abschließendes Urteil? Was lohnt sich für mich mehr?

Es handelt sich insgesamt um eine 9x9 Matrix.

Wichtig ist nur (natürlich) dass es das richtige Ergebnis zurückgibt, kann man diesbezüglich der Breitensuche immer "vertrauen"?

Ich gehe davon aus, dass die A*-Methode schwerer zu implementieren ist, ja?

Lg

Dennis

jaenicke - So 04.01.09 03:01

---

dennismijo hat folgendes geschrieben :

Es handelt sich insgesamt um eine 9x9 Matrix.

Da sollte die Breitensuche auf jeden Fall schnell genug sein.

dennismijo hat folgendes geschrieben :

Wichtig ist nur (natürlich) dass es das richtige Ergebnis zurückgibt, kann man diesbezüglich der Breitensuche immer "vertrauen"?

Ja, die Breitensuche sucht ja immer gleichzeitig alle gleich weit entfernten Felder ab und dann die davon benachbarten usw.
Wenn man also am Zielfeld ankommt, dann hat man immer den kürzesten Weg (bzw. einen der kürzesten, wenn es gleich lange gibt).

dennismijo hat folgendes geschrieben :

Ich gehe davon aus, dass die A*-Methode schwerer zu implementieren ist, ja?

Schwerer nicht unbedingt, wenn man es erst verstanden hat, aufwendiger ist sie aber bei der Implementierung. ;-)

dennismijo - So 11.01.09 21:10

---

Vielen Dank!
Ich habe mal "spaßighalber" beides implementiert. Beides Funktioniert super! ;)