TSP Software 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
D kern (Diskussion | Beiträge) (→NOCH IN BEARBEITUNG !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!) |
(→Theorie) |
||
| Zeile 16: | Zeile 16: | ||
Following this formula the possible solutions raise like this: | Following this formula the possible solutions raise like this: | ||
| − | + | nodes (cities): possible routes: Laufzeit (3GHz Single Core): | |
3 2 0,063 sec | 3 2 0,063 sec | ||
4 6 0,073 sec | 4 6 0,073 sec | ||
Version vom 30. Juni 2013, 14:39 Uhr
Inhaltsverzeichnis
Theorie
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: Laufzeit (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. Laufzeit von n=11 x 12)
13 479.001.600 143,474 sec (ca. Laufzeit von n=12 x 13)
14 6.227.020.800 29,987 min (ca. Laufzeit von n=13 x 14)
15 87.178.291.200 ~ 7,400 h (ca. Laufzeit von n=14 x 15)
16 1.307.674.368.000 ~ 5,000 d (ca. Laufzeit von n=15 x 16)
17 20.922.789.888.000 ~ 85,000 d (ca. Laufzeit von n=16 x 17)
18 355.687.428.096.000 ~ 4,200 y (ca. Laufzeit von n=17 x 18)
19 6.402.373.705.728.000 ~ 80,000 y (ca. Laufzeit von n=18 x 19)
20 121.645.100.408.832.000 ~ 1,600 ty (ca. Laufzeit von 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}
Berechnung einer Route
Wie berechnet der Computer eine Strecke?
Zu allererst muss man dazu wissen wie man den Abstand 2 er Punkte im Koordinatensystem misst. Dazu benutzen wir den Satz des Pythagoras:
Man nehme zwei Punkte A(ax|ay), B (bx|by) im Koordinatensystem. Der Abstand dieser Punkte wäre dann also:
Punktabstand: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sqrt{(ax - bx)^2 + (ay - by)^2}
Wie berechnet der Computer eine Route?
Der Computer misst den Abstand jedes Punktes zu seinem Nachfolger und addiert dann das Ergebnis um so die gesamte Strecke zu bestimmen.
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}
Wie berechnet der Computer die schnellste Route (durch Permutation)?
Er berechnet die Route für jede mögliche Permutation und speichert sich die aktuell kürzeste Strecke ab. Ist eine neu berechnete Strecke kürzer als die Bisherige, so wird diese ersetzt. Wurden für alle möglichen Permutationen die Strecken berechnet, bleibt am Ende nur die kürzeste übrig - diese wird dann ausgegeben.
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
