Detailansicht
Laufzeitanalyse von Iterated Local Search und Simulated Annealing am Traveling Salesman Problem
Reinhard Bazant
Art der Arbeit
Magisterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Walter Gutjahr
DOI
10.25365/thesis.10011
URN
urn:nbn:at:at-ubw:1-30231.39209.357065-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das Problem des Handlungsreisenden ist eines der bekanntesten und meistuntersuchten kombinatorischen Optimierungsprobleme. Es ist bislang kein exakter, polynomialer Lösungsalgorithmus bekannt, weshalb die Analyse der Laufzeit und der Leistungsstärke näherungsweiser Lösungsheuristiken von besonderer Bedeutung ist. Diese Arbeit untersucht die statistische Verteilung der Laufzeit der Methode des simulierten Abkühlens bzw. einer speziellen Variante der iterierten lokalen Suche. Dabei wird einerseits ein Prognosemodell der mittleren Laufzeiten in Abhängigkeit bestimmter problem- bzw. heuristikspezifischer Parameter aufgestellt, andererseits versucht die empirische Verteilung der Laufzeiten durch aus der Statistik bekannte Verteilungen zu approximieren.
Schlagwörter
Schlagwörter
(Deutsch)
Traveling Salesman Problem kombinatorische Optimierung polynomiale Laufzeit simuliertes Abkühlen iterierte lokale Suche Laufzeitprognose Verteilungsanpassung
Autor*innen
Reinhard Bazant
Haupttitel (Deutsch)
Laufzeitanalyse von Iterated Local Search und Simulated Annealing am Traveling Salesman Problem
Publikationsjahr
2010
Umfangsangabe
113 S.
Sprache
Deutsch
Beurteiler*in
Walter Gutjahr
Klassifikationen
31 Mathematik > 31.12 Kombinatorik, Graphentheorie ,
54 Informatik > 54.76 Computersimulation
AC Nummer
AC08224860
Utheses ID
9035
Studienkennzahl
UA | 066 | 951 | |