Simulated Annealing und verwandte Verfahren für das Traveling Salesman Problem
Zur Studie gehört Software, die nur in digitaler Form (CD oder Download) erhältlich ist.
- Art: Diplomarbeit
- Autor: Andy Ruigies
- Abgabedatum: Juli 1995
- Umfang: 79 Seiten
- Dateigröße: 4,6 MB
- Note: 2,0
- Institution / Hochschule: Leibniz Universität Hannover Deutschland
- ISBN (eBook): 978-3-8324-0616-5
-
ISBN (Paperback) :
978-3-8324-0616-5 P - ISBN (CD) :978-3-8324-0616-5 CD
- Sprache: Deutsch
- Prämierung:
- Arbeit zitieren: Ruigies, Andy Juli 1995: Simulated Annealing und verwandte Verfahren für das Traveling Salesman Problem, Hamburg: Diplomica Verlag
- Schlagworte: Great-Deluge-Algorithm, Optimierung, Simulated Annealing, Threshold Accepting, Traveling-Salesman-Problem
In den Warenkorb
38,00 €
Diplomarbeit von Andy Ruigies
Einleitung:
Das Traveling Salesman Problem (TSP) wird mit heuristischen Verfahren näherungsweise gelöst.
Man kann das TSP exakt lösen, aber der Zeitaufwand wächst exponentiell mit der Anzahl der Städte.
Man ist daher bemüht, mit neuartigen Verfahren vorgegebene Probleme näherungsweise zu lösen. In der Praxis ist der Zeitaufwand deutlich geringer und die Güte dieser Lösungen ausreichend.
Das bekannteste heuristische Verfahren ist Simulated Annealing. Es entstand durch Analogien aus der Feststoffphysik und liefert schnell gute Ergebnisse. In dieser Arbeit wird dieses Verfahren mit sowie weitere verwandte Methoden vergleichend angewendet. Dazu wurde in Turbo-Pascal ein Programm geschrieben, das diese Verfahren anwendet. Man kann Größe des Problems sowie das zu verwendende Verfahren eingeben und kann die Ergebnisfindung grafisch anschaulich dargestellt verfolgen.
Inhaltsverzeichnis:
| 1. | Vorwort | 1 |
| 2. | (Historische) Einführung | 3 |
| 2.1 | Das Traveling Salesman Problem | 3 |
| 2.2 | Problematik | 4 |
| 2.3 | Einige bekannte Verfahren zur Lösung des TSP | 4 |
| 2.3.1 | Exakte Verfahren | 4 |
| 2.3.2 | Heuristische Verfahren | 5 |
| 3. | Physikalische und mathematische Grundlagen | 9 |
| 3.1 | Physikalische Grundlagen | 9 |
| 3.2 | Mathematische Grundlagen | 12 |
| 4. | Simulated Annealing | 15 |
| 4.1 | Grundlagen | 15 |
| 4.2 | Implementation: Das Programm travel | 17 |
| 4.2.1 | Grundlegende Implementation | 17 |
| 4.2.2 | Die Benutzerführung des Programms | 21 |
| 5. | Verwandte Verfahren | 26 |
| 5.1 | Threshold Accepting | 26 |
| 5.1.1 | Grundlagen | 26 |
| 5.1.2 | Implementation | 27 |
| 5.2 | Great-Deluge-Algorithmus | 27 |
| 5.2.1 | Grundlagen | 27 |
| 5.2.2 | Implementation | 29 |
| 5.3 | Record-to-record-Travel | 30 |
| 5.4 | Bekannte Fehler des Programms travel | 31 |
| 6. | Bewertung und Vergleich der Ergebnisse | 34 |
| 6.1 | Berechnete Ergebnisse | 34 |
| 6.2 | Vergleich der Ergebnisse | 41 |
| 7. | Erweiterungsmöglichkeiten und Ausblicke | 55 |
| 8. | Anhang | 58 |
| 8.1 | Listing des Programms | 58 |
| 8.1.1 | Das Programm travel | 58 |
| 8.1.2 | Die Grafikbibliotheksgrafik | 70 |
| 8.2 | Literaturverzeichnis | 73 |
In den Warenkorb
38,00 €
Link zur Arbeit:
http://www.diplom.de/ean/9783832406165
Arbeit zitieren:
Ruigies, Andy Juli 1995: Simulated Annealing und verwandte Verfahren für das Traveling Salesman Problem, Hamburg: Diplomica Verlag
Schlagworte:
Great-Deluge-Algorithm, Optimierung, Simulated Annealing, Threshold Accepting, Traveling-Salesman-Problem
Entdecken Sie mehr zum Thema
