Dijkstra-Algorithmus

[Gast]

Hallo, ich möchte den Algorithmus selber ausprogrammieren habe dabei aber eine kleine Verständnisfrage.

Ansich ist ja alles ganz einfach, man wählt einen Start-Knoten und geht jeweils den kürstesten Weg zum nächsten Knoten, der noch nicht in meinem "neuen" Baum ist. Weitere erklärungen spare ich mir, ich denke die die mir helfen können kennen ihn ;-).

Was ist in dem Fall wenn zwei Wege gleich lang sind, wählt man dann einfach per Zufall aus?


Ich probiere mal eine Skizze. Die Kosten zu b und c sind 3. (der Graph geht danach noch weiter, ich habe einen auschnitt gewählt um das Problem zu verdeutlichen - mir ist klar das man sonst in diesem Fall beide Wege nach b und c gehen müsste, damit man alle knoten besucht - darum gehts hier aber nicht ;-) ):



(a)--3--(c)--------------
|
|
3
|
|
(b)
|
|
|
|

[Gast]

Hallo, ich möchte den Algorithmus selber ausprogrammieren habe dabei aber eine kleine Verständnisfrage.

Ansich ist ja alles ganz einfach, man wählt einen Start-Knoten und geht jeweils den kürstesten Weg zum nächsten Knoten, der noch nicht in meinem "neuen" Baum ist. Weitere erklärungen spare ich mir, ich denke die die mir helfen können kennen ihn ;-).

Was ist in dem Fall wenn zwei Wege gleich lang sind, wählt man dann einfach per Zufall aus?ja

[AlSvartr]

Wir haben bei Knoten, die alphabetisch benannt waren, immer den in der lexikalischen Ordnung vor dem anderen liegenden Buchstaben gewählt und sind dann den Weg zu eben diesem Knoten gegangen. Aber das war wohl eher nur, um einfach System reinzubringen...der Zufall sollte es tun.

[Senior Sanchez]

Es ist doch eh egal, welchen man jetzt zuerst besucht *g*
Es werden doch beide besucht, der eine jetzt, der andere eben später.

Oft nutzt man den Dijkstra-Algorithmus ja mit einer Prioritätswarteschlange und da hängts einfach davon ab, wie du die Vergleichsbedingung für die "aufsteigen"- bzw. die "versickern"-Methode formulierst, ob du nur auf größer testest bzw. auf größer gleich.

[robobimbo]

du kanns ja noch so eine art heuristik hinzufügen, zb. wenn du kooridnaten von b und c weisst die mit dem kürzeren geometrischen abstand bevorzugt nehmen (wie es auch gern bei A* Algo gemacht wird)

[Gast]

Alles klar, danke für eure Hilfe !
Und sorry für die Tippfehler, war schon relativ müde... ;-)

[Senior Sanchez]

du kanns ja noch so eine art heuristik hinzufügen, zb. wenn du kooridnaten von b und c weisst die mit dem kürzeren geometrischen abstand bevorzugt nehmen (wie es auch gern bei A* Algo gemacht wird)

Kannste dich mal etwas über den A* Algo auslassen?
Ich habe darüber mal inner Wikipedia gelesen, aber ich fand das dort extrem schwammig formuliert, so nach dem Motto: "Da hat man nun die Heuristik und die benutzt man nun um das ganze einfacher zu machen"

Sprich blabla, ohne konkreter zu werden.

Wennde nen Link hast, der das ganze gut erklärt, wäre das auch super.

[MeLLe]

Kannste dich mal etwas über den A* Algo auslassen?
Ich habe darüber mal inner Wikipedia gelesen, aber ich fand das dort extrem schwammig formuliert, so nach dem Motto: "Da hat man nun die Heuristik und die benutzt man nun um das ganze einfacher zu machen"

Sprich blabla, ohne konkreter zu werden.

Wennde nen Link hast, der das ganze gut erklärt, wäre das auch super.
Vielleicht hift dir das hier (http://www.geocities.com/jheyesjones/astar.html)?

[robobimbo]

oder auch hier, für simples basic *g* - http://www.blitzbase.de/artikel/path_1.htm

[Wanginator]

Kannste dich mal etwas über den A* Algo auslassen?
Ich habe darüber mal inner Wikipedia gelesen, aber ich fand das dort extrem schwammig formuliert, so nach dem Motto: "Da hat man nun die Heuristik und die benutzt man nun um das ganze einfacher zu machen"

Sprich blabla, ohne konkreter zu werden.

Wennde nen Link hast, der das ganze gut erklärt, wäre das auch super.

Also ich finde das bei Wikipedia ganz gut dargestellt, besonders das Städtebeispiel. Grob gesagt betrachtet A* die Knoten die offen liegen, also im nächsten Schritt besucht werden können und wählt den dazu, der am vielversprechensten aussieht. Dies ermittelt die Heuristik, die die tatsächlichen Kosten bis zu jenem Knoten und optimistisch geschätzte Kosten bis zum Zielknoten addiert.

Ein schönes Applet findest du hier: http://www.vision.ee.ethz.ch/~buc/astar/AStar.html

[Senior Sanchez]

Also ich finde das bei Wikipedia ganz gut dargestellt, besonders das Städtebeispiel. Grob gesagt betrachtet A* die Knoten die offen liegen, also im nächsten Schritt besucht werden können und wählt den dazu, der am vielversprechensten aussieht. Dies ermittelt die Heuristik, die die tatsächlichen Kosten bis zu jenem Knoten und optimistisch geschätzte Kosten bis zum Zielknoten addiert.

Ein schönes Applet findest du hier: http://www.vision.ee.ethz.ch/~buc/astar/AStar.html

Hmm, stimmt, die Seite scheint im August etwas überarbeitet worden zu sein. Als ich das letzte Mal geschaut habe, war das noch nich so.

Danke für das Applet, ich schaus mir mal an.