Kürzester Weg mehrere Punkte

Neue Frage »

wegsucher Auf diesen Beitrag antworten »
Kürzester Weg mehrere Punkte
Meine Frage:
Hallo!
Ich möchte den kürzest möglichen Weg berechnen um ca. 20 bis 30 verschiedene Punkte zu verbinden. Die Punkte liegen auf einer Ebene, die Koordinaten bzw. die Entfernung zwischen den einzelnen Punkten sind bekannt.

Meine Ideen:
Muß ich wirklich alle Möglichkeiten durchrechnen oder gibt es andere Ansätze?
Alle Möglichkeiten wären meiner Meinung nach 30x29x28....../2 Rechenoperationen.
Ich habe schon selbst einen Versuch gemacht und immer nur die nähesten 5 Punkte für die nächste Berechnung herangezogen. Das funktioniert am Anfang, aber die entferntesten Punkte werden dabei links liegen gelassen und müssen am Ende mit sehr langen Wegen erreicht werden. Geht also nicht!

Danke im Voraus für Eure Hilfestellungen!

p.s.: Ich bin kein Mathematiker, beherrsche eigentlich nur die Grundrechnungsarten und programmiere noch in dbase.....
HAL 9000 Auf diesen Beitrag antworten »

Geht es um das Traveling Salesman Problem (TSP) ?
wegfinder Auf diesen Beitrag antworten »
Kürzester Weg mehrere Punkte
Ja, im Prinzip geht es um das Problem des Handlungsreisenden. Ich habe gar nicht gewusst, dass darüber schon so viel geschrieben wurde....
Ich muss mich erst einlesen, sicher finde ich Hilfestellungen, die ich gebrauchen kann.
Etwas ist mir dabei schon klar geworden: Ich muss mich rechtzeitig um die entferntesten Punkte kümmern und diese zum richtigen Zeitpunkt ansteuern.

Mein Problem (Problem des Friedhofsgärtners) unterscheidet sich vom Problem des Handlungsreisenden allerdings bezüglich der Anzahl der anzusteuernden Punkte und ist auf max. ca. 30 Punkte begrenzt.

Noch einen Ansatzpunkt habe ich: Vielleicht sollte ich Paare von einander naheliegenden Punkten bilden und dann wirklich jede Möglichkeit rechnen? Wären dann 14x13x12x11...../2 Möglichkeiten. Schafft das mein PC?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »