Startseite    
MathematikPoolNRW Projekt Hintergründe Kontakt




Kombinatorische Optimierung / Die Berechnung kürzester Wege


Die Einführung in die Kombinatorische Optimierung befasst sich mit der Berechnung kürzester Wege in Graphen. Dazu soll das prinzipielle Vorgehen des Dijkstra-Verfahrens erläutert, an Beispielen demonstriert und seine Korrektheit bewiesen werden.

Der Benutzer hat die Möglichkeit, bestehende Programme auf gegebene oder von ihm zu erzeugende Beispielgraphen anzuwenden und interaktiv zu testen.

Die Einführung setzt sich aus vier Komponenten zusammen:

• 
einem Kursteil, der aus einer Einführung in die Fragestellung und in die benötigten Begriffe der Graphentheorie, einer Darstellung des Grundalgorithmus (Dijkstra), einem formalen Beweis seiner Korrektheit und einer Laufzeitanalyse besteht.
• 
einem interaktiv-benutzbarem Programmeditor, der erlaubt, in Python geschriebene Programmecodes zu interpretieren. Die Programme können als Video durchlaufen, schrittweise abgearbeitet werden oder von Stopmarke zu Stopmarke laufen, die vom Benutzer gesetzt werden können.
Für die Editierung der Programme kann ein beliebiger Texteditor benutzt werden.
• 
einem Demonstrationsfenster, in dem an Hand konkreter Beispiele die Funktionsweise und der Ablauf der Programme illustriert wird.
• 
einem Grapheneditor, der es ermöglicht, Graphen selbst zu erzeugen bzw. zu verändern.


Die letzten drei Komponenten basieren auf der Graphenvisualisierungssoftware Gato (Graph Animation Toolbox), welche am ZAIK (Zentrum für Angewandte Informatik Köln) entwickelt wurde. Gato ist unter der GPL (Gnu Public License) veröffentlicht und läuft unter Unix, Linux, MacOS und Windows 9x/ME/NT/XP mittels Python.

Um die Beispielprogramme auf den folgenden Seiten ausführen zu können, wird jedoch eine modifizierte Version von Gato, welche auch ohne Python läuft, benötigt.
Diese ist verfügbar für:
• 
Windows:
mit Netscape und MS Internet Explorer Unterstützung
• 
Linux:
mit Netscape 4.x/6 und Mozilla Unterstützung (benötigt tcl/tk-8.3)
• 
Solaris:
mit Netscape 4.x/6 Unterstützung (benötigt tcl/tk-8.3)

Nach dem Download muss Gato wie folgt installiert werden:
1. 
Die heruntergeladene Datei ausführen:
  - Unter Windows einfach auf "Gato.exe" doppelklicken.
  - Unter Linux den Befehl "chmod u+x Gato.lin && ./Gato.lin" ausführen.
  - Unter Solaris den Befehl "chmod u+x Gato.sol && ./Gato.sol" ausführen.
2. 
Im Menü Files den Menüpunkt Install Gato auswählen.
3. 
Evtl. das Standardinstallationsverzeichnis ändern - jedoch alles andere unverändert lassen.
4. 
Auf OK klicken und Gato beenden.
5. 
Evtl. den Web-Browser neu starten, falls Gato nicht erkannt wird.

Nun sollte Ihr Browser automatisch Gato ausführen, wenn Sie auf den folgenden Seiten auf ein Beispielprogramm mit der Endung ".gato" klicken und die darauf folgende Browserabfrage mit "Öffnen" bestätigen.