Title (deu)
Laufzeitanalyse von Iterated Local Search und Simulated Annealing am Traveling Salesman Problem
Author
Reinhard Bazant
Advisor
Walter Gutjahr
Assessor
Walter Gutjahr
Abstract (deu)
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.
Keywords (deu)
Traveling Salesman Problemkombinatorische Optimierungpolynomiale Laufzeitsimuliertes Abkühleniterierte lokale SucheLaufzeitprognoseVerteilungsanpassung
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1266593
rdau:P60550 (deu)
113 S.
Number of pages
113
Association (deu)
Title (deu)
Laufzeitanalyse von Iterated Local Search und Simulated Annealing am Traveling Salesman Problem
Author
Reinhard Bazant
Abstract (deu)
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.
Keywords (deu)
Traveling Salesman Problemkombinatorische Optimierungpolynomiale Laufzeitsimuliertes Abkühleniterierte lokale SucheLaufzeitprognoseVerteilungsanpassung
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1266594
Number of pages
113
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0