Simulated Annealing und verwandte Verfahren für das Traveling Salesman Problem: Zur Studie gehört Software, die nur in digitaler Form (CD oder Downloa

ISBN-13: 9783838606163 / Niemiecki / MiÄ™kka / 1998 / 84 str.

Andy Ruigies

Opis

Diplomarbeit aus dem Jahr 1995 im Fachbereich Mathematik - Angewandte Mathematik, Note: 2,0, Gottfried Wilhelm Leibniz Universitat Hannover (Unbekannt), Sprache: Deutsch, Abstract: Inhaltsangabe: Einleitung: Das Traveling Salesman Problem (TSP) wird mit heuristischen Verfahren naherungsweise gelost. Man kann das TSP exakt losen, aber der Zeitaufwand wachst exponentiell mit der Anzahl der Stadte. Man ist daher bemuht, mit neuartigen Verfahren vorgegebene Probleme naherungsweise zu losen. In der Praxis ist der Zeitaufwand deutlich geringer und die Gute dieser Losungen 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 Grosse des Problems sowie das zu verwendende Verfahren eingeben und kann die Ergebnisfindung grafisch anschaulich dargestellt verfolgen. Inhaltsverzeichnis: Inhaltsverzeichnis: 1.Vorwort1 2.(Historische) Einfuhrung3 2.1Das Traveling Salesman Problem3 2.2Problematik4 2.3Einige bekannte Verfahren zur Losung 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 Benutzerfuhrung 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.Erweiterungsmoglichkeiten und Ausblicke55 8.Anhang58 8.1Listing des Programms58 8.1.1Das Programm travel58"