Titelaufnahme

Titel
Implementierung und Visualisierung von Heuristiken für das Traveling Salesman Problem / Martin Pinter
Verfasser/ VerfasserinPinter, Martin
Begutachter / BegutachterinPferschy Ulrich
Erschienen2010
Umfang43 Bl. : Zsfassung ; graph. Darst.
HochschulschriftGraz, Univ., Masterarb., 2010
Anmerkung
Zsfassung in engl. Sprache
SpracheDeutsch
DokumenttypMasterarbeit
Schlagwörter (GND)Travelling-salesman-Problem / Heuristik / Travelling-salesman-Problem / Heuristik / Online-Publikation
URNurn:nbn:at:at-ubg:1-73416 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Implementierung und Visualisierung von Heuristiken für das Traveling Salesman Problem [0.83 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Die gegenständliche Arbeit beschreibt ausgewählte programmiertechnische Grundlagen des Programms GEHIM welches im Rahmen dieser Diplomarbeit in Java programmiert wurde. Die Hauptarbeit war die Entwicklung und Programmierung des Programms GEHIM, welches als erweiterungsfähige Plattform für Problemstellungen der Graphentheorie dient. Der Quellcode von GEHIM besteht aus ca. 14.000 Zeilen (inkl. Kommentaren, ohne Leerzeilen, ohne Hilfe-Dateien).Das Programm GEHIM ermöglicht neben der einfachen Erstellung, Speicherung und dem Laden von Graphen für TSP Fragestellungen auch die Anwendung von Eröffnungs- sowie Verbesserungsalgorithmen. Die Ergebnisse werden schrittweise berechnet und sollen einerseits Benutzern mit wenigen Vorkenntnissen die Nachvollziehung der Berechnungsschritte ermöglichen. Andererseits ist das Programm in der Lage auch sehr komplexe Graphen mit bis zu 600 Knoten zu Verarbeiten und zu Berechnen. Besonderes Augenmerk wurde auf die graphische Ausgabe der Daten gelegt. So existiert neben der Möglichkeit einen Graphen über eine graphische Benutzeroberfläche mit wenigen Mouse-Eingaben zu erstellen, ein Modul welches via Knoten-Triangulation die Koordinaten der Knoten euklidischer metrischer Graphen, aus den Entfernungen der Knoten zueinander berechnet. Damit können Graphen mit wenigen Grundinformationen, unabhängig von der Speicherstruktur der importierten Graphen, graphisch dargestellt werden. Für das zeitextensive Erstellen von Graphen stellt GEHIM Fenster zur Verfügung in welchen Graphen mit wenigen Mouse-Eingaben erstellt werden können. Dies dient nicht nur dem einfachen und schnellen Erstellen, und der Visualisierung von Graphen, sondern ermöglicht auch die Anwendung der Verbesserungsalgorithmen auf selbst erstellte Touren. Sämtliche Aktualisierungsroutinen sind auf höchstmögliche Performance optimiert.Diese Arbeit beschreibt die Strukturen der verwendeten Arrays und Algorithmen im Programm und beinhaltet eine kurze Bedienungsanleitung für den User.

Zusammenfassung (Englisch)

This master thesis describes technical program basics of the program GEHIM. GEHIM was programmed for this thesis. The source code of GEHIM consists of about 14,000 lines (including comments, without blank lines, without help function) and is the base of this thesis.GEHIM enables basic functions as construction, saving and loading of graphs. It also provides routines for construction heuristics and improvement heuristics. Results are calculates and shown step by step. This provides that inexperienced users can retrace intermediate steps and understand the calculated heuristics. On the other hand the program is able to deal with large graphs of up to 600 nodes. Particular attention was paid to the graphical output of the data. A special module provides via node triangulation that the coordinates of single nodes are calculated from the data of distances from euclidean metric graphs, to be drawn on the screen. Independent of the saving structure of the graphical data of an imported graph with few information the graph can be visualized. In addition to this module GEHIM provides a user interface window where graphs can be drawn with few mouse inputs. Nodes and edges can be set and deleted. This also provides that improvement heuristics can be used on self-made graphs. There also exists the possibility to drag nodes, change direction of the graph and delete edges. All inputs have real time effects on the relevant data. Different update routines ensure that just the relevant data are changed and provide maximum performance.This thesis sketches the internal design of GEHIM. It describes the structure of the main arrays and procedures. It also sketches the use of GEHIM although a full context sensitive help function is implemented in the Program.