TSP Software 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 24: | Zeile 24: | ||
mögliche Routen: in diesem Fall also 6. | mögliche Routen: in diesem Fall also 6. | ||
| + | |||
[[Datei:Rundreisen.png]] | [[Datei:Rundreisen.png]] | ||
Version vom 24. Juni 2013, 13:00 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 usw.) 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; jeden Punkt kann also frei mit jedem anderen Punkt verbunden werden.
---
Außerdem gibt es verschiedene Arten von TSPs:
- ---
Beispiel
Um eine Städtereise zu planen bei denen 4 verschiedene Städte angefahren werden sollen, gibt es
(n - 1)!
mögliche Routen: in diesem Fall also 6.
Typische Problemstellung
fewfwefwef
Lösungsansätze
Code Beispiel:
Hier folgt Code (Leerzeichen vorstellen)
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
