Lade Inhalt...

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.

©1995 Diplomarbeit 79 Seiten

Zusammenfassung

Inhaltsangabe: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:Inhaltsverzeichnis:
1.Vorwort1
2.(Historische) Einführung3
2.1Das Traveling Salesman Problem3
2.2Problematik4
2.3Einige bekannte Verfahren zur Lösung des TSP4
2.3.1Exakte Verfahren4
2.3.2Heuristische Verfahren5
3.Physikalische und mathematische Grundlagen9
3.1Physikalische Grundlagen9
3.2Mathematische Grundlagen12
4.Simulated Annealing15
4.1Grundlagen15
4.2Implementation: Das Programm travel17
4.2.1Grundlegende Implementation17
4.2.2Die Benutzerführung des Programms21
5.Verwandte Verfahren26
5.1Threshold Accepting26
5.1.1Grundlagen26
5.1.2Implementation27
5.2Great-Deluge-Algorithmus27
5.2.1Grundlagen27
5.2.2Implementation29
5.3Record-to-record-Travel30
5.4Bekannte Fehler des Programms travel31
6.Bewertung und Vergleich der Ergebnisse34
6.1Berechnete Ergebnisse34
6.2Vergleich der Ergebnisse41
7.Erweiterungsmöglichkeiten und Ausblicke55
8.Anhang58
8.1Listing des Programms58
8.1.1Das Programm travel58
8.1.2Die Grafikbibliotheksgrafik70
8.2Literaturverzeichnis73

Leseprobe

Inhaltsverzeichnis


Details

Seiten
Erscheinungsform
Originalausgabe
Jahr
1995
ISBN (eBook)
9783832406165
ISBN (Paperback)
9783838606163
DOI
10.3239/9783832406165
Dateigröße
4.5 MB
Sprache
Deutsch
Institution / Hochschule
Gottfried Wilhelm Leibniz Universität Hannover – Unbekannt
Erscheinungsdatum
1998 (Januar)
Note
2,0
Schlagworte
great-deluge-algorithm optimierung simulated annealing threshold accepting traveling-salesman-problem
Zurück

Titel: Simulated Annealing und verwandte Verfahren für das Traveling Salesman Problem
book preview page numper 1
book preview page numper 2
book preview page numper 3
book preview page numper 4
book preview page numper 5
book preview page numper 6
book preview page numper 7
book preview page numper 8
book preview page numper 9
book preview page numper 10
book preview page numper 11
book preview page numper 12
book preview page numper 13
book preview page numper 14
book preview page numper 15
book preview page numper 16
book preview page numper 17
79 Seiten
Cookie-Einstellungen