Krain Geschrieben 9. November 2004 Geschrieben 9. November 2004 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 Geschrieben 9. November 2004 Geschrieben 9. November 2004 Stichwort Transportkostenoptimierung, sofern der Kostenbetrag den Kilometern zwischen den Punkten betrifft. Die Berechnungen darauf sind ziemlich vielschichtig, aber logisch. PS: Google mal!
Krain Geschrieben 9. November 2004 Autor Geschrieben 9. November 2004 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 Geschrieben 9. November 2004 Geschrieben 9. November 2004 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 Geschrieben 9. November 2004 Geschrieben 9. November 2004 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 Geschrieben 9. November 2004 Autor Geschrieben 9. November 2004 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 Geschrieben 9. November 2004 Geschrieben 9. November 2004 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 Geschrieben 9. November 2004 Geschrieben 9. November 2004 Oder auf deutsch das Problem des Handlungsreisenden... Schau mal hier: http://www.jgiesen.de/Divers/TSM/TSM.html mit Code
kLeiner_HobBes Geschrieben 9. November 2004 Geschrieben 9. November 2004 läßt sich IMHO am besten mit einer Abbildung eines neuronalen Netzes in einem Algorithmus lösen.
speedi Geschrieben 9. November 2004 Geschrieben 9. November 2004 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 Geschrieben 9. November 2004 Geschrieben 9. November 2004 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 Geschrieben 9. November 2004 Autor Geschrieben 9. November 2004 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 Geschrieben 26. Juni 2006 Geschrieben 26. Juni 2006 Hallo, ich suche eine Lösung in Delphi zu dem Problem des Handlungsreisenden. Kann mir da jemand weiterhelfen? Bitte, bitte....
alwi Geschrieben 27. November 2023 Geschrieben 27. November 2023 Ich habe das Problem gelöst, es gibt hierfür ein C-Programm von mit. Interesse ? alfred.witzl@googlemail.com
allesweg Geschrieben 27. November 2023 Geschrieben 27. November 2023 Du bietest die Lösung für ein 17 Jahre altes Problem an, ohne die Bezugskonditionen zu nennen? Kann man so machen...
Empfohlene Beiträge