Algorithmus des kuerzesten Weges

S

Sancheck

Legendäres Mitglied
Hallo,
ich habe einige Punkte (es geht hier nicht um ein NAVI etc.) sondern nur um vl. 50 Punkte.

Nun moechte ich den Weg abfahren. zwischen diesen Punkten.

Der kuerzeste Weg ist von relevanz.
Ich habe von jedem Punkt x und y Koordinaten.
Meine Idee:
Ich berechne mir mittels

laenge = sqrt((x1-x2)^2+(y1-y2)^2)

zwischen ALLEN Punkten die laengen,... das sind dann 50! werte(! steht fuer Fakultaet)

Naja und das reihe ich dann und fange mit dem kuerzesten Wert an....bis ich alle abgefahren habe,...

Mein Gedankengang richtig?
 
Hallo,

vielleicht solltest du dir den Dijkstra-Algorithmus mal anschauen. Nicht erschrecken...sieht vielleicht auf den ersten Blick etwas kompliziert aus, ist aber eigentlich sehr einfach.

Es gibt meines Wissens auch schon viele Implementierungen in den unterschiedlichsten Programmiersprachen.

Grüße
Oli
 
Hallo,
danke.
smile.gif

nein der hilft mir hier nichts da ich ALLE Punkte anfahren muss
 
...ok, ich verstehe. Du hast einen Startpunkt von dem aus du alle Knoten nacheinander, mit minimaler weglänger erreichen willst...?

Dann könnten minimale Spannbäume interessant für dich sein. Mit dem Algorithmus von Kruskal kannst du solche minimalen Spannbäume berechnen. In dem Artikel sind unten auch 2 Java-Applets verlinkt...da kannst du ja ein wenig damit rumspielen.

Hilft das vielleicht?

Grüße
Oli

PS.: wenn es sich bei dir um eine einmalige Sache handelt, dann fährst du wohl mit deinem (naiven) Ansatz auch nicht schlecht. Allerdings wirst du dort wohl nicht den kürzesten weg finden...nur einen kurzen
smile.gif


PPS: http://de.wikipedia.org/wiki/Algorithmus_von_Prim als Alternative zu dem von Kruskal
 
1. Gibt es einen Weg von jedem Punkt zu jedem Punkt? Das wäre ein Spezialfall.
2. Es gibt nicht 50! Längen. Du sollst nicht Formeln anwenden, sondern nachdenken. Mal 5 Punkte aufs Papier. Dort wirst Du nicht 5!=120 sondern 10 Wege haben. 4+3+2+1=10.
3. Mit dem kürzesten Weg anzufangen wird nur den ersten Teilabschnitt in der schnellsten Zeit erreichen.
4. Dijkstra löst das Problem NICHT! Es ist das Problem des Handlungsreisenden, bzw. das Eulerkreisproblem (sofern Deine Lösung verlangt, dass Du jeden Punkt nur einmal besuchst).
5. Ein Spannbaum löst das Problem auch nicht. (Du musst bei einem Spannbaum bestimmte Wege doppelt gehen, d.h. der minimale Spannbaum ist eine obere Schranke des kürzesten Wegs, d.h. ist höchstens doppelt so lange wie der minimale Weg).

Der Spannbaum ist aber der erste Schritt zum genausten Ansatz. Die beste Heuristik - so meine ich - ist die Christofides-Heuristik. Die maximale Abweichung ist 50%.

QUOTE Naja und das reihe ich dann und fange mit dem kuerzesten Wert an....bis ich alle abgefahren habe,...

Diese Heuristik hat sogar einen Namen, die des nächsten-Nachbarns. Leider ist die Abweichung zum kürzesten Weg beliebig gross. D.h. u.U. erhälts Du nicht einmal einen kurzen, sondern einen beliebig langen Weg.

Bei 50 Punkten kannst Du mit Brute Force die richtige Lösung errechnen.

Das dürfte für Dich interessant sein:
http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
 
Meine Loesung ist unter Umstaenden nicht die ideale.
Ich habe die Abstaende zwischen allen punkten ermittelt.
Das geht bei 50 Stueck noch ganz gut
also 50+49+48,...Stueck sind das.
Nun habe ich gereiht.Den kuerzesten Weg von meiner Startposition genommen. Dann wieder den kuerzesten usw. Das fuehrt im realen zu einem Netzartigen Ablauf.
Das heisst, ich laufe tatsaechlich einen relativ optimierten Weg ab.
 
Sie müssen sich einloggen oder registrieren, um hier antworten zu können.
Zurück
Oben