Ein Handlungsreisender soll eine gewisse Anzahl von Kunden in verschiedenen Städten besuchen, in jeder Stadt einen Kunden, und anschließend zum Ausgangspunkt zurückkehren. Doch wie ist diese Reise zu wählen, sodass der Handlungsreisende den möglichst kürzesten Gesamtweg beschreitet? Diese Fragestellung wird als das Problem des Handlungsreisenden bzw. das Traveling Salesman Problem (kurz TSP) bezeichnet.
Diese etwas einfache Beschreibung trifft die Gesamtheit des Problems aber bei weiten nicht. Bei dem Problem des Handlungsreisenden handelt es sich um ein Minimierungsproblem aus dem Bereich der theoretischen Informatik. Genauer gesagt gehört es zu einer sehr wichtigen Klasse der theoretischen Informatik; den sogenannten NP-vollständigen Problemen, für die keine effizienten und exakten Lösungsverfahren existieren bzw. existieren können (unter der Annahme das P≠NP gilt).
Intuitiv kann ein Mensch mit Blick auf eine Karte und einer geringen Anzahl an Städten, die es für eine Rundreise zusammenzuführen gilt, eine gute, gar optimale, Lösung sehen. Dieses gilt aber nicht für Maschinen und Softwareprogramme, denn diese können die Gesamtheit nicht wie ein Mensch begreifen. Somit müssen andere, konkretere, Lösungen genutzt werden.
Ziel dieser Arbeit ist es, einen Überblick über die Geschichte, Definition und Arten des Problems des Handlungsreisenden zu geben. Die Einordnung in der theoretischen Informatik zu klassifizieren und zu beschreiben sowie eine ausführliche Übersicht und Beschreibung von bekannten exakten und annähernden Lösungsverfahren zu geben. Ziel soll ein Kompendium für das Problem des Handlungsreisenden sein.
Für diese Arbeit wird vorausgesetzt, dass der Leser grundlegende Kenntnisse der Mathematik, Graphentheorie und theoretischen Informatik besitzt.
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
Zielsetzung & Themen
Das primäre Ziel dieser Arbeit ist die Erstellung eines umfassenden Kompendiums zum Traveling Salesman Problem (TSP), das dessen historische Entwicklung, theoretische Einordnung in der Informatik sowie eine detaillierte Gegenüberstellung von exakten und approximativen Lösungsverfahren bietet.
- Historische Entwicklung und Rekorde des TSP
- Klassifizierung in der Komplexitätstheorie (NP-Vollständigkeit)
- Analyse exakter Lösungsverfahren wie Brute Force und Dynamische Programmierung
- Untersuchung von Approximationsalgorithmen und Heuristiken
- Praktische Anwendungsbereiche und Optimierungsmethoden
Auszug aus dem Buch
3.2. Dynamische Programmierung
Eine schnellere Möglichkeit, um das Problem des Handlungsreisenden exakt zu lösen, bietet die in der Informatik verbreitete Technik der Rekursion bzw. eine spezielle Variante: die dynamische Programmierung. Bei diesem Verfahren wird ein Problem in mehrere Teilprobleme aufgeteilt, die rekursiv gelöst werden. Durch die Lösung der Teilprobleme soll eine Lösung für das Hauptproblem zusammengeführt werden. Es werden zunächst nur kleinere Probleme von dem Algorithmus bearbeitet. Anschließend wird die Lösung immer weiter auf größere Teilmengen des vorliegenden Problems ausgebreitet. Die dynamische Programmierung löst die Teilprobleme somit aufsteigend, beginnend mit dem kleinsten Teilproblem. Die Lösungen der Teilprobleme werden in einer Tabelle so lange gespeichert, wie sie benötigt werden, um keine wiederholten Berechnungen von bereits gelösten Teilproblemen durchzuführen.
Zusammenfassung der Kapitel
1. Einleitung und Motivation dieser Arbeit: Einführung in das TSP als Rundreiseproblem und Definition der Zielsetzung dieser Arbeit.
2. Definitionen, Konventionen, Begriffe und Problemstellung des TSP: Mathematische Fundierung, historische Meilensteine sowie Einordnung des TSP in die Komplexitätstheorie.
3. TSP exakt lösen: Vorstellung von Algorithmen zur exakten Lösungsfindung inklusive deren exponentieller Laufzeitkomplexität.
4. Approximierbarkeit des TSP: Analyse heuristischer Lösungsverfahren, die in polynomieller Zeit akzeptable Ergebnisse liefern.
5. Fazit und Ausblick: Zusammenfassende Betrachtung der Relevanz des TSP und Ausblick auf weiterführende Forschungsansätze.
Schlüsselwörter
Traveling Salesman Problem, TSP, Komplexitätstheorie, NP-vollständig, Rundreiseproblem, Optimierung, Heuristik, Brute Force, Dynamische Programmierung, Branch and Bound, Nearest Neighbor, Christofides, Lin-Kernighan, Approximation, Graphentheorie
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt das klassische Problem des Handlungsreisenden (Traveling Salesman Problem) und bietet eine strukturierte Übersicht über theoretische Grundlagen sowie bekannte Lösungsstrategien.
Was sind die zentralen Themenfelder?
Die Arbeit fokussiert auf die mathematische Definition, die Komplexitätsklassen (NP), exakte Algorithmen und approximative Heuristiken zur Lösung des Rundreiseproblems.
Was ist das primäre Ziel der Forschungsarbeit?
Ziel ist es, ein wissenschaftliches Kompendium zu erstellen, das alle relevanten Aspekte des TSP zusammenfasst und als Referenz für Informatik-Interessierte dient.
Welche wissenschaftlichen Methoden werden verwendet?
Es erfolgt eine literaturbasierte Analyse und Aufarbeitung von Algorithmen und komplexitätstheoretischen Beweisen, ergänzt durch grafische Veranschaulichungen.
Was wird im Hauptteil behandelt?
Im Hauptteil werden sowohl exakte Verfahren (wie Brute Force, Dynamische Programmierung) als auch Näherungsverfahren (Insertion-Heuristiken, K-Opt) detailliert beschrieben.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die wichtigsten Begriffe sind Traveling Salesman Problem, NP-Vollständigkeit, Heuristiken, Optimierung, Graphentheorie und Algorithmen.
Warum ist das Problem des Handlungsreisenden so schwierig zu lösen?
Das TSP gehört zur Klasse der NP-vollständigen Probleme, für die bisher keine effizienten, exakten Algorithmen existieren, deren Laufzeit bei wachsender Stadtanzahl polynomiell bleibt.
Was unterscheidet exakte von approximativen Verfahren?
Exakte Verfahren garantieren die optimale Lösung, benötigen aber oft exponentielle Rechenzeit. Approximative Verfahren (Heuristiken) liefern in kurzer Zeit „gute“, aber nicht zwangsläufig optimale Lösungen.
- Arbeit zitieren
- Kai Pohl (Autor:in), 2013, Das Problem des Handlungsreisenden. Ein Kompendium, München, GRIN Verlag, https://www.grin.com/document/265472
