Titel:
Lösung des Traveling Salesman Problems und Darstellung in einer Webapplikation
Beteiligte:
Lotz, Sebastian
[Verfasser:in]
Erschienen:
Munich University of Technology (TUM): mediaTUM, 2014
Sprache:
Deutsch
Entstehung:
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Seit seiner ersten Beschreibung im Jahr 1930 ist das Traveling Salesman Problem eines der prominentesten Beispiele ungelöster Probleme der kombinatorischen Optimierung. Es fragt auf einem vollständigen, symmetrischen Graphen nach einem kürzesten Ha- miltonkreis. Im ersten Teil der vorliegenden Arbeit werden grundlegende Verfahren zur Lösung des Problems vorgestellt. Dazu zählen die beiden Heuristiken Nearest-Neighbor und Multiple-Fragment. Als Vertreter exakter Lösungsverfahren wird eine auf Eins-Bäumen basierende Lagrange-Relaxierung in Verbindung mit dem Branch-and-Bound-Algorithmus betrachtet. Diese Verfahren sind Teil der in der zweiten Hälfte beschriebenen Webapplikation, die im Zuge der Arbeit erstellt wurde. Sie dient der anschaulichen Darstellung der Algorith- men mit dem Ziel, Schülern und Studenten Methoden der kombinatorische Optimierung näherzubringen. Die Applikation bedient sich dabei neuester Webtechnologien wie HTML 5 und jQuery.