kürzester Weg zwischen beliebigen Punkten

[Krain]

Hallo zusammen,

Mein Problem ist folgendes:

Ich habe ein Array aus verschiedenen Orten.

Nun brauche ich aus diesen Orten die kürzeste Strecke, ohne ein bestimmte Reihenfolge, einen bestimmten Start- oder Zielpunkt anzugeben!

Es muss allerdings jeder Punkt angefahren werden.

Entfernungen sind bekannt!

Wie ist der beste Ansatz dafür!?

gruss

markus

[Der Kleine]

Stichwort Transportkostenoptimierung, sofern der Kostenbetrag den Kilometern zwischen den Punkten betrifft.

Die Berechnungen darauf sind ziemlich vielschichtig, aber logisch.

PS: Google mal!

[Krain]

Ich dachte mir, ich mach ein Array aus möglichen Permutationen und berechne deren Längen und nehme dann einfach dir Kürzeste!

Nun aber das zweite Problem, woher bekomm ich einen Algorithmus, der mir alle möglichen Permutationen bestimmt?

Oder hat jemand dazu eine Idee? Ich hatte schon ein paar ansätze, aber die sind alle in die Hose gegangen!

[kingofbrain]

Servus,

das Stichwort ist Dijkstra. Der Dijkstra-Algorithmus bestimmt Dir den kostengünstigsten Weg in einem Netzwerk.

Google mal danach, der ist eigentlich recht einfach, eine Implementierung habe ich aber leider auch nicht.

Hier ist eine kleine Erklärung und Veranschaulichung: http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm

Peter

[ssambdar]

Genau das habe ich auch gerade herausgefunden. Einen weiteren Guten Link zu dem Thema findest du hier: http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml

[Krain]

Das passt aber auch nicht ganz! Ich will alle Punkte in einer Linie bzw. Strecke abfahren ohne an einem Punkt zweimal vorbei zu kommen.

Der Dijkstra sucht doch nur den kürzesten weg zu einem beliebigen endpunkt!

Stellt es euch mal so vor:

Ich schmeiße fünf kugeln auf den boden und suche jetzt den kürzesten weg zwischen diesen um sie auf einmal abzufahren!

Wie gehe ich am besten vor!?

Djikstra sagt mir nur wie ich am kürzesten von Kugel1 zu Kugel3 oder Kugel5 komme.

Ich will aber im Allgemeinen nur die kürzeste Strecke zwischen allen Punkten ohne einen Punkt doppelt anzufahren!

[Klotzkopp]

Das passt aber auch nicht ganz! Ich will alle Punkte in einer Linie bzw. Strecke abfahren ohne an einem Punkt zweimal vorbei zu kommen.

Das ist das Travelling Salesman Problem (wenn man die Rückkehr zum Startpunkt weglässt).

Bisher ist kein Algorithmus bekannt, der das Problem schneller als exponentiell löst. Du kannst natürlich alle möglichen Routen durchprobieren, aber bei vielen Punkten wird das sehr bald sehr langsam.

Um wieviele Punkte geht es denn?

[blackyK4]

Oder auf deutsch das Problem des Handlungsreisenden...

Schau mal hier: http://www.jgiesen.de/Divers/TSM/TSM.html mit Code

[kLeiner_HobBes]

läßt sich IMHO am besten mit einer Abbildung eines neuronalen Netzes in einem Algorithmus lösen.

[speedi]

Geht es hier um Städte oder um irgendwelche koordinaten? Fährst du auf Straßen oder Quer feldein was willst du eigentlich? Hast du mehrere Ponkte in nen KOS die du verbinden musst? :confused:

[Bubble]

Das TSP gehört zur Klasse der NP-harten und NP-vollständigen Probleme. Es hat eine Komplexität von O(n!), deswegen wird die vollständige Lösung bei ausreichend vielen Städten sehr viel Zeit benötigen.

Es gibt allerdings verschiedene Ansätze, mit denen man zwar nicht immer den besten (kürzesten) Weg findet, aber eine gute Nährung bei geringerem Aufwand erreicht. Einfach mal im Web suchen.

Eine vollständige Lösung durch Probieren aller Permutationen macht nur bei wenigen Städten Sinn. Wenn man den Startpunkt beliebig wählt, kann man die Zahl der zu prüfenden Verbindungen reduzieren, die Komplexität des Problems an sich sinkt damit aber leichter nicht.

[Krain]

Es sind Punkte auf einer Karte, der Einfachheit halber werden nur die Entfernung luftlinie betrachtet.

Ich hab mir schon einiges darüber durchgelesen und werde mich wohl für die Lösung mit dem neuronalen Netz entscheiden!

Ich habe einige imposante Applets dazu gesehen und bin davon überzeugt, dass es mit diesen funktioniert!

Das ausprobieren würde bei mir nicht funktionieren, da es sich teilweise um mehr als 15 oder 20 Punkte handeln kann!

Danke für eure Hilfen!

gruss

markus

[DerKleineGrisu]

Hallo,

ich suche eine Lösung in Delphi zu dem Problem des Handlungsreisenden. Kann mir da jemand weiterhelfen?

Bitte, bitte....

[alwi]

Ich habe das Problem gelöst,

es gibt hierfür ein C-Programm von mit.

Interesse ?

alfred.witzl@googlemail.com

[allesweg]

Du bietest die Lösung für ein 17 Jahre altes Problem an, ohne die Bezugskonditionen zu nennen?

Kann man so machen...