TSP Software 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
(→Lösungsverfahren) |
(→Lösungsverfahren) |
||
| Zeile 85: | Zeile 85: | ||
- [http://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Nearest Neighbor] | - [http://de.wikipedia.org/wiki/Nearest-Neighbor-Heuristik Nearest Neighbor] | ||
| + | |||
- [http://de.wikipedia.org/wiki/Nearest-Insertion-Heuristik Nearest Insertion Heuristik] | - [http://de.wikipedia.org/wiki/Nearest-Insertion-Heuristik Nearest Insertion Heuristik] | ||
Version vom 26. Juni 2013, 14:49 Uhr
Inhaltsverzeichnis
NOCH IN BEARBEITUNG !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Theorie
Das 'Traveling Salesman Problem' (auch 'Problem des Handlungsreisenden') ist ein kombinatorisches Optimierungsproblem. Dabei besteht auf Aufgabe darin, eine optimale Reihenfolge für den Besuch von Knotenpunkten (z.B. Städte, Bohrungen ect.) zu finden. Das Kriterium, welches es dabei zu minimieren gilt, kann unterschiedlich sein; beispielweise kann es sinnvoll sein die Wegstrecke (Längeneinheiten), die Zeit (Zeiteinheiten) und/oder die Kosten (Geldeinheiten) oder eine Mischung aus diesen Kriterien heran zu ziehen.
Des Weiteren gibt es unterschiedliche Restriktionen für die TS-Problemantik:
Um das Beispiel so einfach wie möglich zu halten, minimieren wir die Wegstrecke und grenzen Kanten (z.B. Straßen) aus; jeder Punkt kann also frei mit jedem anderen Punkt verbunden werden.
Beispiel:
Um eine Städtereise zu planen bei denen 4 verschiedene Städte (A, B, C, D) angefahren werden sollen, gibt es (n - 1)! mögliche Routen: In diesem Fall also (4 - 1)! = 6.
In diesem Fall sind die Graphen gerichtet - es gibt also zwei unterschiedliche Wege eine Route zu befahren (auch die optimale Route).
Nach dieser Formel steigt die mögliche Lösungsmenge also mit jeder weiteren Stadt wie folgt an:
Städte: mögliche Routen: 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)
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.
Exakte Lösungsverfahren
- Branch and Bound (Branch and Cut)
Heuristiken
Lösungsansätze
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)!
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
