TSP Software 1: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Berechnung einer Route) |
(→Calculation of a route) |
||
Zeile 37: | Zeile 37: | ||
== Calculation of a route == | == Calculation of a route == | ||
+ | |||
'''How does the computer calculate the distance?''' | '''How does the computer calculate the distance?''' | ||
Zeile 45: | Zeile 46: | ||
Take 2 points A(ax|ay), B (bx|by). The distance of those points is: | Take 2 points A(ax|ay), B (bx|by). The distance of those points is: | ||
<math>\sqrt{(ax - bx)^2 + (ay - by)^2}</math> | <math>\sqrt{(ax - bx)^2 + (ay - by)^2}</math> | ||
+ | |||
'''How does the computer calculate a route?''' | '''How does the computer calculate a route?''' | ||
− | |||
The computer measures the distance of every point to his successor and adds the results to get the distance of the whole route: | The computer measures the distance of every point to his successor and adds the results to get the distance of the whole route: | ||
− | |||
− | |||
+ | <math>\sum_{i=0}^{n-1} \sqrt{(a_{i}x - b_{i}x)^2 + (a_{i}y - b_{i}y)^2}</math> | ||
Version vom 30. Juni 2013, 14:49 Uhr
Inhaltsverzeichnis
Theory
The 'Traveling Salesman Problem' (or 'travelling salesperson problem') is an NP-hard problem in combinatorial optimization. Its exercise is to find the optimal route for the visit of nodes. The criterion, which is to minimize, can be different; e.g. the time it takes, the costs, the distance or a mix of these.
Furthermore there are diffrent kind of restrictions for the TSP: To make the example as simple as possible we minimize the distance and use coordinate system, so every point can be related to every other point.
Example:
To plan a road trip with 4 different cities (A, B, C, D) there are Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (n - 1)!
possible routes: In this case Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (4 - 1)! = 6
.
Following this formula the possible solutions raise like this:
nodes (cities): possible routes: runtime (3GHz Single Core): 3 2 0,063 sec 4 6 0,073 sec 5 24 0,078 sec 6 120 0,109 sec 7 720 0,125 sec 8 5.040 0,156 sec 9 4.0320 0,187 sec 10 262.880 0,265 sec 11 3.628.800 1,279 sec 12 39.916.800 12,293 sec (ca. runtime of n=11 x 12) 13 479.001.600 143,474 sec (ca. runtime of n=12 x 13) 14 6.227.020.800 29,987 min (ca. runtime of n=13 x 14) 15 87.178.291.200 ~ 7,400 h (ca. runtime of n=14 x 15) 16 1.307.674.368.000 ~ 5,000 d (ca. runtime of n=15 x 16) 17 20.922.789.888.000 ~ 85,000 d (ca. runtime of n=16 x 17) 18 355.687.428.096.000 ~ 4,200 y (ca. runtime of n=17 x 18) 19 6.402.373.705.728.000 ~ 80,000 y (ca. runtime of n=18 x 19) 20 121.645.100.408.832.000 ~ 1,600 ty (ca. runtime of n=19 x 20)
Calculation of a route
How does the computer calculate the distance?
First of all u have to know how to measure the distance of 2 points in a coordinate system. Therefor we use the Pythagoras' theorem:
Take 2 points A(ax|ay), B (bx|by). The distance of those points is: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sqrt{(ax - bx)^2 + (ay - by)^2}
How does the computer calculate a route?
The computer measures the distance of every point to his successor and adds the results to get the distance of the whole route:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{n-1} \sqrt{(a_{i}x - b_{i}x)^2 + (a_{i}y - b_{i}y)^2}
How does the computer calculate the fastest route (permutations)?
He calculates the route for every possible permutation and saves the actual shorest distance.
If a new route is shorter than the old one, he saves the new one.
As soon as all possible permutations are computated, there is only the shortest route saved - this will be printed.
Lösungsverfahren
Um das TSP zu lösen ist eine Vielzahl von Algorithmen und Heuristiken bekannt, die teilweise in OR behandelt werden. Hier eine kleine Auswahl:
Exakte Lösungsverfahren
- Branch and Bound (Branch and Cut)
Heuristiken
Implementiertes Verfahren
(Ähnlichkeiten zu RANDIN-Algorithmus)
Man betrachte drei Punkte im Koordinaten System A, B, C mit beliebigen Koordinaten, wobei A der Start und Endpunkt darstellt. Um einen Kreislauf zu bilden hat man nun 2 Möglichkeiten ((3-1)! = 2! = 2):
A -> B -> C-> A
A -> C -> B -> A
Beide Kreisläufe haben jedoch die gleiche Strecke, da sich lediglich die Richtung ändert.
Damit wissen wir, dass egal wie wir 3 Punkte im Koordinatensystem verbinden, wir immer die optimale Strecke haben. Genau hier setzt unsere Heuristik an. Es werden 3 beliebige Punkte ausgewählt, über die wir wissen, dass ihre Verbindungsstrecke optimal ist:
A -> B -> C -> A
Kommt jetzt ein weiterer beliebiger Punkt D hinzu, so wird überprüft, an welcher Stelle D einzusetzen ist, damit die Router weiterhin optimal bleibt:
A->B -> C -> D -> A
A->B -> D -> C -> A
A->D -> B -> C -> A
Die Heuristik braucht bei 4 Punkten also 3 Möglichkeiten zu berechnen während die Permutation 6 bräuchte. Dieser Unterschied ist bei wenigen Punkten noch vernachlässigbar klein, aber mit wachsender Punktanzahl steigt dieser Unterschied stark an (s. Tabelle).
Wir nehmen einmal an A->B -> C -> D -> A wäre optimal.
Soll nun ein weiterer beliebiger Punkt E angefahren werden, so wird wieder die vorher optimale Strecke verwendet um zu überprüfen, an welcher Stelle Punkt E optimal in die Route integriert werden kann:
A->B -> C -> D -> E -> A
A->B -> C -> E -> D -> A
A->B -> E-> C -> D -> A
A->E -> B-> C -> D -> A
Wieder wird die beste Kombination ausgewählt um dann einen weiteren Punkt hinzuzufügen.
Auf diese Weise braucht der Computer nur Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{n-1} i
Schritte anstatt Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (n-1)!
Die Resultate decken sich - wie im folgenden Beispiel zu sehen - oft mit der optimalen Lösung, wobei nur ein Bruchteil der Zeit benötigt wird:
13 Knoten:
60 Knoten:
Quellen
- Wikipedia Eintrag zum TSP ausführliche Informationen zum Traveling Salesman Problem
- Algorithmus der Woche TSP oder die optimale Tour für den Nikolaus
- Online Touren-Planer kostenloser TSP-Solver zur Routenoptimierung