Bachelorarbeit, 2013
44 Seiten, Note: 1.3
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
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!
Kommentare