Toleranzen in Helsgauns Lin-Kernighan-Heuristik für das TSP
Autor: | Dirk Richter |
---|---|
EAN: | 9783836494748 |
eBook Format: | |
Sprache: | Deutsch |
Produktart: | eBook |
Veröffentlichungsdatum: | 06.05.2008 |
Kategorie: | |
Schlagworte: | Backbones Double-Bridge LKH Lin-Kernighan-Heuristik TSP Toleranzen Traveling Salesman Problem |
59,00 €*
Versandkostenfrei
Die Verfügbarkeit wird nach ihrer Bestellung bei uns geprüft.
Bücher sind in der Regel innerhalb von 1-2 Werktagen abholbereit.
Das Ziel dieser Arbeit war die Verbesserung der Helsgaun-Heuristik, welche zu den weltbesten Heuristiken für das Travelling Saleman Problem (TSP) gehört und u.A. derzeit die beste bekannte Tour für das berühmte World-TSP geliefert hat. Durch die Fortschritte dieser Diplomarbeit können nun viele Probleminstanzen in geringerer Zeit gelöst werden und es werden teilweise auch bessere Touren im Vergleich zur Heuristik von Helsgaun gefunden. Bereits während der Diplomarbeit konnte der Weltrekord für ein VLSI-Problem (xsc6880) von 21537 Kosten auf 21535 Kosten verbessert werden. Insgesamt konnten einige Vermutungen widerlegt und andere vermutete Zusammenhänge anschaulich nachgewiesen werden. Neben eher abstrakten Modifikationen im allgemeinen Verfahren wurden auch verschiedene Aspekte der bestehenden Implementation untersucht, erweitert und verbessert. Und es wurden wichtige neue theoretische Erkenntnisse aufgeführt und bewiesen.
Geboren 1981 in Halle (Saale). Von 2001 bis 2006 studiert er Informatik und war auch darüber hinaus noch als wissenschaftliche Hilfskraft im DFG-Projekt der Martin-Luther-Universität Halle tätig, wo er seit 2006 im Lehrstuhl 'Softwaretechnik und Programmiersprachen' promoviert.
Geboren 1981 in Halle (Saale). Von 2001 bis 2006 studiert er Informatik und war auch darüber hinaus noch als wissenschaftliche Hilfskraft im DFG-Projekt der Martin-Luther-Universität Halle tätig, wo er seit 2006 im Lehrstuhl 'Softwaretechnik und Programmiersprachen' promoviert.