Wie berechnet man die kürzeste Strecke entlang 11 Wegpunkten?
An die Mathematiker der Seite ;)
Ich suche eine Möglichkeit die kürzeste Verbindung 11 fester Punkte in einem 2-Dimensionalen Koordinatensystem zu finden.
Zusätzlich: Gibt es eine zweite (andere) Verbindung ebendieser Punkte, wobei die Punktreihenfolge nach Länge der Verbindungen zwischen den Punkten geordnet ist? Also so, dass P1-P2 die kürzeste und P10-P11 die längste Strecke ist?.
Hintergrund ist, dass ich eine Laufstrecke durch die Stadt entlang 11 Bestimmter Gebäude plane (siehe dazu auch die dazu gestellte Frage auf meinem Profil).
Ich habe bereits die Entfernung jedes Punktes zu jedem anderen Punkt (mit Google Maps) gemessen, allerdings bin ich mit meinem mathematischen Halbwissen ein wenig überfragt 😅.
Viel Spaß beim ausknobeln😂.
3 Antworten
die kürzeste Verbindung 11 fester Punkte
Wenn der Start- und Endpunkt frei wählbar sind, entspricht das einem TSP mit einem 12. Punkt, der zu allen anderen den Abstand 0 hat. Dafür gibt es keinen effizienten Algorithmus, aber bei 11 Punkten kann man alle 11! ≈ 40 Millionen Möglichkeiten schnell im Computer durchprobieren.
Punktreihenfolge nach Länge der Verbindungen zwischen den Punkten geordnet
Das klingt spannend! Aber schau Dir mal diese vier Punkte an:
: :
Ich finde da schon keine Lösung, bei der die Abstände in jedem Schritt wachsen (oder gleich bleiben) :-(
Du kannst höchstens die Bedingung aufweichen (d.h. zu kurze Folgeschritte mit Strafpunkten belegen) und dann einen Pfad mit minimalen Strafpunkten suchen. Auch das geht bei 11 Punkten recht flott.
Wenn Du die 11×11-Abstandsmatrix postest, rechne ich das gern mal durch.
Ich habe jetzt in Excel mithilfe des Solver-Tools und dem Evolutionären Algorithmus die Verbindung
6 7 8 9 11 10 5 4 3 2 1
mit den Werten
0.6 1.2 0.9 2.1 1.4 2.3 0.95 2.7 0.55 0.7 2.1 = 15.5 km
gefunden.
Wie würden Sie es berechnen und bezüglich der weiteren Parameter (aus der Frage oben) weiter vorgehen?
Ich komme auf (4, 5, 3, 2, 1, 6, 7, 8, 9, 10, 11) mit (0.95, 2.6, 0.55, 0.7, 2.1, 0.6, 1.2, 0.9, 0.8, 1.4) = 11.8 km.
Der zweitbeste Pfad ist (4, 5, 3, 1, 2, 6, 7, 8, 9, 10, 11) mit (0.95, 2.6, 1.2, 0.7, 1.5, 0.6, 1.2, 0.9, 0.8, 1.4) = 11.85 km.
Die Strecke misst aber nur den Weg vom Startpunkt (4) zum Endpunkt (11), ohne Rückfahrt von 11 nach 4.
Eine kürzeste Rundfahrt hat tatsächlich 15.5 km. Dafür gibt es 2 verschiedene Lösungen:
- (1, 2, 3, 4, 5, 10, 11, 9, 8, 7, 6)
- (1, 2, 3, 4, 5, 11, 10, 9, 8, 7, 6)
Dein Graph hat 91 Pfade mit aufsteigenden Abständen. Der mit der kürzesten Gesamtstrecke ist (2, 1, 3, 7, 10, 8, 6, 5, 9, 4, 11). Er hat die Länge 19.9 km, die Rundreise hat 23.8 km. Die Abschnitte sind (0.7, 1.2, 1.3, 1.4, 1.7, 1.7, 2.2, 2.6, 3.1, 4.0) + 3.9 für den Rückweg.
Die kürzeste Rundreise mit 23.65 km bei 22.95 km Strecke hat der Pfad (2, 3, 7, 10, 8, 6, 5, 9, 4, 11, 1). Seine Abschnitte sind (0.55, 1.3, 1.4, 1.7, 1.7, 2.2, 2.6, 3.1, 4.0, 4.4) + 0.7 für den Rückweg.
Ich habe den Rückweg vom End- zum Startpunkt bei der Berechnung nicht bewertet. Er kann also kürzer als die letzte Teilstrecke und länger als die erste sein. Melde Dich, wenn Du etwas anderes brauchst.
Unglaublich :)
Vielen vielen Dank, das hat mir sehr weitergeholfen. Soweit sind meine Wünsche alle erfüllt, allerdings hätte ich noch eine letzte Nachfrage. Wäre es möglich, dass Sie noch den kürzesten Pfad mit Endpunkt 10 und den kürzesten Pfad mit wachsenden Schritten und Endpunkt 10 (falls realisierbar) berechnen?
Natürlich nur wenn es ihnen keine Umstände bereitet, bis dahin bedanke ich mich auf jeden fall schon einmal für die geleistete Hilfe.
LG
Die kürzesten Rundreisen bleiben natürlich dieselben, weil man da den Startpunkt frei wählen kann. Außerdem kannst Du vorwärts oder rückwärts laufen. Das sind dann vier verschiedene Lösungen, die bei 10 enden.
Die kürzeste Strecke hat der Pfad (4, 5, 3, 2, 1, 6, 7, 8, 9, 11, 10) mit den Abschnitten (0.95, 2.6, 0.55, 0.7, 2.1, 0.6, 1.2, 0.9, 2.1, 1.4) + 2.8 Rückweg. Seine Länge ist 13.1 km, eine Rundreise hat 15.9 km. Das ist nur wenig schlechter als das allgemeine Optimum.
Es gibt aber keinen wachsenden Pfad mit Endpunkt 10. Die beste Näherung, die ich gefunden habe, ist der Pfad (6, 2, 9, 5, 3, 4, 7, 11, 8, 1, 10) mit den Abschnitten (1.5, 2.3, 2.6, 2.6, 2.7, 2.7, 2.7, 2.9, 2.7, 3.1) + 1.1 Rückweg. Seine Länge ist 25.8 km, eine Rundreise hat 26.9 km. Bei der Suche habe ich die Pfade so bewertet, dass die Differenzen bei zu kleinen Folgepfaden aufsummiert werden. Hier gibt es nur einmal (ziemlich am Ende) 2.9–2.7=0.2 Strafpunkte.
Mit einer anderen Bewertungsfunktion könnte es andere „akzeptable“ Pfade geben. Allerdings gibt es bei allen Pfaden mit Ende 10 mindestens einen Abschnitt, der um mindestens 0.2 kürzer als sein Vorgänger ist. Daher nehme ich an, dass die obige Näherungslösung so oder so das beste ist, was Du kriegen kannst.
Alles klar, damit bin ich dann endgültig zufrieden :)
Nochmals vielen Dank für die schnelle Hilfe und einfachen Erklärungen.
1 2 3 4 5 6 7 8 9 10 11
1 0.0 0.7 1.2 3.7 3.6 2.1 2.2 2.7 2.9 3.1 4.4
2 0.7 0.0 0.55 3.1 3.0 1.5 1.6 2.1 2.3 2.5 3.9
3 1.2 0.55 0.0 2.7 2.6 1.2 1.3 2.1 2.0 2.2 3.6
4 3.7 3.1 2.7 0.0 0.95 2.3 2.7 3.7 3.1 2.8 4.0
5 3.6 3.0 2.6 0.95 0.0 2.2 2.5 3.2 2.6 2.3 3.6
6 2.1 1.5 1.2 2.3 2.2 0.0 0.6 1.7 1.2 1.1 2.5
7 2.2 1.6 1.3 2.7 2.5 0.6 0.0 1.2 0.85 1.4 2.7
8 2.7 2.1 2.1 3.7 3.2 1.7 1.2 0.0 0.9 1.7 2.9
9 2.9 2.3 2.0 3.1 2.6 1.2 0.85 0.9 0.0 0.8 2.1
10 3.1 2.5 2.2 2.8 2.3 1.1 1.4 1.7 0.8 0.0 1.4
11 4.4 3.9 3.6 4.0 3.6 2.5 2.7 2.9 2.1 1.4 0.0
Hier nochmal die Matrix in ordentlich.
Das ist das wohlbekannte "Traveling Salesman Problem"
https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
Hallo,
ich suche auch ein Programm oder Excel Tabelle mit Formel oder so, wo ich die 16 Koordinaten des Planeten eingeben kann und er mir die kürzeste Strecke angibt.
Gibt es sowas?
Zb diese Koordinaten chronologisch ordnen kann sodass man die kürzeste Strecke hat :
01: -62.29, +44.43 # 02: -40.65, +15.22
03: +44.73, -14,34 # 04: +30.29, +173.29
05: -25.73, -173.29 # 06: +13.19, +37.14
07: -53.34, -37.77 # 08: -75.15, -160.56
09: +19.80, +44.78 # 10: +9.88, -147.69
11: +54.16, +128.39 # 12: +29.40, +169.18
13: -29.20, +48.81 # 14: -61.95, -152.02
15: +15.29, +24.86 # 16: +47.92, -12.23
Danke im Vorraus 😊
Okay alles klar, habe mich schon gewundert ob die zu berechnende Menge zu groß für einen durchschnittlichen Computer sei.
Das zum Teil mit den Abständen habe ich auch überlegt, allerdings kann man das doch bestimmt rechnerisch herausfinden, ob es dazu eine oder mehrere bzw. keine Lösung gibt.
Die Abstandsmatrix lautet wie folgt, gegen Probleme der Leserlichkeit werde ich zusätzlich einen fileshare-link einer .txt datei per Privatnachricht schicken:
Atom 1 2 3 4 5 6 7 8 9 10 11
1 0.0 0.7 1.2 3.7 3.6 2.1 2.2 2.7 2.9 3.1 4.4
2 0.7 0.0 0.55 3.1 3.0 1.5 1.6 2.1 2.3 2.5 3.9
3 1.2 0.55 0.0 2.7 2.6 1.2 1.3 2.1 2.0 2.2 3.6
4 3.7 3.1 2.7 0.0 0.95 2.3 2.7 3.7 3.1 2.8 4.0
5 3.6 3.0 2.6 0.95 0.0 2.2 2.5 3.2 2.6 2.3 3.6
6 2.1 1.5 1.2 2.3 2.2 0.0 0.6 1.7 1.2 1.1 2.5
7 2.2 1.6 1.3 2.7 2.5 0.6 0.0 1.2 0.85 1.4 2.7
8 2.7 2.1 2.1 3.7 3.2 1.7 1.2 0.0 0.9 1.7 2.9
9 2.9 2.3 2.0 3.1 2.6 1.2 0.85 0.9 0.0 0.8 2.1
10 3.1 2.5 2.2 2.8 2.3 1.1 1.4 1.7 0.8 0.0 1.4
11 4.4 3.9 3.6 4.0 3.6 2.5 2.7 2.9 2.1 1.4 0.0
Vielen Dank für's Helfen :)
LG