Leseprobe
Inhaltsverzeichnis
1. Einleitung und Motivation dieser Arbeit
2. Definitionen, Konventionen, Begriffe und Problemstellung des TSP
2.1. Aktuelle Ergebnisse und Rekorde - Die Geschichte des TSP
2.2. Einordnung des TSP
2.2.1. Komplexitätstheorie
2.2.2. Entscheidungs- und Optimierungsproblem
2.2.3. TSP in NP und NP-schwere des Problems
2.3. Asymmetrisches, symmetrisches und metrisches TSP
2.4. Hamiltonischer Kreis (Hamiltonkreis) und Euler Weg
2.5. Multiple-TSP (mTSP) und Vehicle Routing Problem (VRP)
3. TSP exakt lösen
3.1. Brute Force
3.2. Dynamische Programmierung
3.3. Branch and Bound
4. Approximierbarkeit des TSP
4.1. Nearest Neighbor und Greedy
4.2. Insertion Heuristiken
4.3. Minimum Spanning Tree (MST)
4.4. Christofides
4.5. K-Opt Verbesserungsverfahren
4.6. Lin-Kernighan (LK) und Lin-Kernighan-Helsgaun (LKH)
5. Fazit und Ausblick
7. Literaturverzeichnis
8. Abbildungsverzeichnis
- Arbeit zitieren
- Kai Pohl (Autor:in), 2013, Das Problem des Handlungsreisenden. Ein Kompendium, München, GRIN Verlag, https://www.grin.com/document/265472
Ähnliche Arbeiten
Kostenlos Autor werden
Kommentare