Grundlegende Algorithmen des Travelling Salesman Problems (TSP)
- Art: Diplomarbeit
- Autor: Stefan Spreitzer
- Abgabedatum: Juli 2001
- Umfang: 171 Seiten
- Dateigröße: 591,2 KB
- Note: 1,0
- Institution / Hochschule: Fachhochschule Westküste, Heide Deutschland
- ISBN (eBook): 978-3-8324-4387-0
-
ISBN (Paperback) :
978-3-8324-4387-0 P - ISBN (CD) :978-3-8324-4387-0 CD
- Sprache: Deutsch
- Prämierung:
- Arbeit zitieren: Spreitzer, Stefan Juli 2001: Grundlegende Algorithmen des Travelling Salesman Problems (TSP), Hamburg: Diplomica Verlag
- Schlagworte: Algorithmen, Travelling Salesman Problem, TSP, Visual Basic 6.0-Programm
In den Warenkorb
58,00 €
Diplomarbeit von Stefan Spreitzer
Problemstellung:
Das „Travelling-Salesman-Problem“ (TSP), auch bekannt als „Problem des Handelsreisenden“, ist wohl das am meisten beachtete Optimierungsproblem aus dem Bereich des Operations Research. Hierbei soll ein Handelsreisender, ausgehend von einem beliebigem Startort x0, n verschiedene Städte genau einmal bereisen und anschließend wieder an den Startort x0 zurückkehren. Aus den insgesamt n! möglichen Touren soll nun die kürzeste Rundreise ermittelt werden, wobei die Entfernungen der einzelnen Orte zum Startort sowie zueinander bekannt sind.
Das Kernproblem des TSP liegt im nicht ponentiellen Wachstum der möglichen Touren bei steigender Anzahl der zu bereisenden Orte, so dass verschiedene Algorithmen zum Einsatz kommen, die versuchen, sich dem Optimum so schnell wie möglich anzunähern.
In der hier vorliegenden Arbeit sollen nun einige auserwählte Algorithmen in Visual Basic 6.0 umgesetzt werden, wobei darauf hingewiesen wird, daß es sich um rein symetrische TSP’s handelt.
Gang der Untersuchung:
Zunächst werden im Abschnitt 2 wichtige Definitionen für das Verständnis der angewandten Algorithmen dargelegt und näher erläutert. Anschließend werden im dritten Abschnitt dieser Arbeit die umgesetzten Algorithmen behandelt.
Abschnitt 4 bildet den eigentlichen Kern der Arbeit. Hierin werden die Hauptprozeduren des Visual Basic-Programms in Form von Struktogrammen visualisiert und ausgiebig erläutert.
Im fünften Abschnitt werden ausgehend von einem Rundreisebeispiel mit 25 Elementen, Ergebnisse und Rechenzeiten der hier vorgestellten Algorithmen tabellarisch festgehalten und bewertet.
Der sechste und letzte Abschnitt dieser Arbeit dient der persönlichen Reflexion der bearbeiteten Thematik.
Inhaltsverzeichnis:
| 1. | Einleitung | 3 |
| 2. | Grundlegende Definitionen | 4 |
| 2.1 | Metrik als allgemeiner Abstand | 4 |
| 2.2 | Euklidischer Abstand | 5 |
| 2.3 | Potential eines Ortes | 5 |
| 2.4 | Savingwert | 6 |
| 2.5 | Permutationen | 7 |
| 2.6 | Längenbetrachtungen | 7 |
| 2.7 | Mittelwert | 8 |
| 2.8 | Standardabweichung | 8 |
| 2.9 | Bewertung nach Chebychev-Markov übertragen auf das TSP | 9 |
| 3. | Kurzpräsentation der angewandten Verfahren | 10 |
| 3.1 | Algorithmus des besten Nachbarn | 12 |
| 3.2 | Inselalgorithmus | 13 |
| 3.3 | Vollenumeration | 14 |
| 3.4 | Anmerkung zur Länge einer Tour | 15 |
| 4. | Visual Basic 6.0 Programm | 16 |
| 4.1 | Datenbankentwurf | 16 |
| 4.2 | Datenbankzugriff | 17 |
| 4.3 | Datenbankmanipulation | 18 |
| 4.3.1 | Elemente hinzufügen | 18 |
| 4.3.2 | Elemente entfernen | 20 |
| 4.4 | Klassenmodul Tourenverkettung | 21 |
| 4.5 | Algorithmen | 24 |
| 4.5.1 | Algorithmus des besten Nachbarn | 24 |
| 4.5.2 | Inselalgorithmus | 27 |
| 4.5.3 | Vollenumeration | 30 |
| 4.6 | Wartungs- und Änderungsdienst | 32 |
| 5. | Rundreisebeispiel mit 25 Elementen | 33 |
| 6. | Schlußbetrachtungen | 35 |
| Literaturverzeichnis | 36 | |
| Anhang | 37 |
In den Warenkorb
58,00 €
Link zur Arbeit:
http://www.diplom.de/ean/9783832443870
Arbeit zitieren:
Spreitzer, Stefan Juli 2001: Grundlegende Algorithmen des Travelling Salesman Problems (TSP), Hamburg: Diplomica Verlag
Schlagworte:
Algorithmen, Travelling Salesman Problem, TSP, Visual Basic 6.0-Programm
Entdecken Sie mehr zum Thema
