Programmumgebung

(Auszug aus Kapitel 2 -> Inhaltsverzeichnis)


Die Unit TSP stellt basierend auf den Units MAUS und GRAFIK eine grafische Benutzeroberfläche und eine einfache Programmierumgebung für Traveling Salesman- und verwandte Probleme zur Verfügung. Die Hilfsprogramme TSP_PROT, KURZPROT und PAS_FORM erlauben die Auswertung von Serienberechnungen bzw. die formatierte Ausgabe von Programmlistings und anderen Dateien, TSP_ALG faßt die in den folgenden Kapiteln vorgestellten Algorithmen zusammen.

Benutzeroberfläche

Abbildung 2.1: Benutzeroberfläche


Programmbedienung

Die Unit TSP stellt für alle Programme der Kapitel 3-6 eine einheitliche Benutzeroberfläche bestehend aus den folgenden Komponenten zur Verfügung (Abb. 2.1):

  1. Titelleiste mit Schließknopf

    Mit dem Schließknopf in der rechten oberen Ecke kann das Programm nach einer Sicherheitsabfrage beendet werden.

  2. Karte

    Hier werden die Städte (max. 75) und Wege angezeigt. Mit der linken Maustaste kann eine Stadt hinzugefügt werden; falls schon eine Entfernungstabelle vorhanden ist, wird diese entsprechend dem gewählten Typ (aus Karte/symmetrisch/asymmetrisch, vgl. Menüpunkt 'Entfernungen') ergänzt. Mit einem rechten Mausklick wird die dem Mauszeiger nächstgelegene Stadt entfernt. Unabhängig von der verwendeten Bildschirmauflösung wird für die Karte ein Koordinatensystem der Größe 1241x1000 mit dem Ursprung in der linken oberen Ecke verwendet.

  3. rechte Menüleiste (s. u.)

  4. Status-, Untermenü- und Eingabeleiste

    Am unteren Bildschirmrand werden abwechselnd Informationen über die angezeigte Rundreise (auf blauem Hintergrund), Untermenüs und Eingabezeilen (grüner Hintergrund) oder Fehlermeldungen (roter Hintergrund) angezeigt. Standardmäßig und nach Klick mit der linken Maustaste findet man dort die aktuelle Tourlänge, mit der rechten Maustaste erhält man statt dessen den Wegtyp. Dabei bedeutet:

    Ist der Weg unterbrechungsfrei, so erhöht sich der Wert um 10, enthält er alle Städte, um 100. Ein Hamiltonscher Kreis hat also den Wegtyp 113.

Über die Punkte der rechten Menüleiste lassen sich die folgenden Funktionen aufrufen:

  1. Neu

    Löscht nach einer Sicherheitsabfrage alle Städte samt Weg und die Entfernungstabelle.

  2. Städte ergänzen

    Es wird eine einzugebende Anzahl von Städten mit zufälliger Lage hinzugefügt. Eine vorhandene Entfernungstabelle wird wieder entsprechend dem gewählten Typ ergänzt.

  3. Städte löschen

    Nach dem Anklicken der ersten und letzten Stadt werden alle potentiell zu löschenden Punkte eingefärbt und nach einer Sicherheitsabfrage entfernt.

  4. Entfernungen

    Berechnet eine neue Entfernungstabelle oder zeigt die vorhandene an. Der Abstand zwischen zwei Städten kann dabei entweder aus der Karte gewonnen werden, in diesem Fall enthält man ein metrisches TSP, oder zufällig symmetrisch oder asymmetrisch gewählt werden. Eine manuelle Eingabe ist durch Edieren einer gespeicherten Aufgabenstellung möglich. Beim Anzeigen großer Tabellen kann mit der linken Maustaste oder der Leertaste vorwärts geblättert werden, ein vorzeitiger Abbruch erfolgt mit der rechten Maustaste oder 'q', 'x' oder 'e'.

  5. Weg

    Ein neuer Weg kann automatisch nach Nummern oder zufällig definiert werden, wobei man jeweils eine Tour erhält, oder manuell bestimmt werden. Im manuellen Fall wird mit der linken Maustaste die nächste Stadt gewählt oder mit der rechten die vorherige entfernt. Über die untere Menüleiste kann zusätzlich eine Unterbrechung eingefügt oder der ganze Weg gelöscht werden. Falls vorhanden, ist neben der Neudefinition eines Weges auch das Aufrufen des vorherigen oder die Überlagerung von vorherigem und aktuellem Weg möglich, wodurch z. B. die Ergebnisse verschiedener Verfahren verglichen oder optimierende Algorithmen auf die gleiche Rundreise angewandt werden können.

  6. Verfahren

    Dieser Menüpunkt ist nur vorhanden, falls die Variable VERFANZAHL (s. 2.2.3) einen Wert größer eins hat, d. h. daß mehrere Verfahren vorhanden sind, von denen eines bestimmt werden kann. Wenn der Algorithmus eine automatische Startpunktwahl (d. h. Berechnung für alle Startpunkte und Wahl des besten, s. 4.1.2) erlaubt, so erfolgt eine entsprechende Abfrage.

  7. Berechnen

    Startet die Berechnung. Falls keine Städte oder keine Entfernungstabelle vorhanden sind oder der Wegtyp nicht den Bedingungen des Algorithmus entspricht, erhält man eine Fehlermeldung. Für diesen Menüpunkt kann vom Programm auch ein anderer Name gewählt werden.

  8. Serie

    Über diesen Punkt ist die automatisierte Berechnung einer Serie von Aufgabenstellungen möglich. Diese müssen als TSP-Dateien mit Namen der Form 'abc*defg.hij' vorliegen, wobei '*' für 0, 1, ... , 9, A, B, ... steht und sich an beliebiger Stelle befinden kann. Die Angabe der Namen zum Speichern erfolgt in gleicher Weise, Optionen bei der Eingabe sind unter 'Speichern' näher erläutert.

    Bei der Serienbearbeitung wird automatisch erkannt, ob eine Ausgabedatei schon existiert und in diesem Fall die Berechnung übersprungen. Dadurch ist es möglich, abgebrochene oder ergänzte Serien fortzusetzen. Am rechten Rand der Statusleiste wird jeweils das für '*' im Dateinamen des gerade bearbeiteten Serienteils eingesetzte Zeichen angezeigt.

  9. Drucken

    Gibt eine Hardcopy der Karte auf Epson- oder Hewlett-Packard-kompatiblen Druckern aus.

  10. Speichern

    Speichert die aktuellen Daten ab. Bei der Eingabe des Dateinamens wird durch '$', evtl. mit nachfolgender Pfadangabe und Dateimaske (z. B. 'A:\*.*', ohne wird '*.TSP' benutzt) das Directory angezeigt, in dem man analog zur Entfernungstabelle blättern kann. Enthält der Name keine Erweiterung, so wird '.TSP' ergänzt, mit einem Leerstring kann man den Vorgang abbrechen. Wie das folgende Beispiel zeigt, erfolgt das Abspeichern im Klartext (ASCII-Format), so daß Änderungen mit einem beliebigen Editor möglich sind:

       1: #TSP V3.02, letzte Rechenzeit: 0.00 s
       2: 
       3: #Städteanzahl
       4: 5
       5: 
       6: #Art der Entfernungsberechnung(0: aus Karte, 1: symmetrisch, 2: asymmetrisch)
       7: 0
       8: 
       9: #Entfernungstabelle
      10: #1
      11:      0.000   652.553   830.533   502.118   552.342
      12: #2
      13:    652.553     0.000   356.753   437.104   661.906
      14: #3
      15:    830.533   356.753     0.000   778.525   999.674
      16: #4
      17:    502.118   437.104   778.525     0.000   224.864
      18: #5
      19:    552.342   661.906   999.674   224.864     0.000
      20: 
      21: #vorheriger Weg(-1: Ende), Länge: 2401.596
      22:    1   5   4   2   3   1  -1
      23: #aktueller Weg(-1: Ende), Länge: 2401.596
      24:    2   3   1   5   4   2  -1
      25: 
      26: #Städtekoordinaten(Maxx: 1240, Maxy: 999)
      27:  947 430
      28:  296 475
      29:  168 142
      30:  598 791
      31:  758 949
    

    '#'-Zeichen erklären den Rest der Zeile zum Kommentar, der beim Laden überlesen wird, Leerzeichen und Zeilenumbrüche wirken als Trennungen zwischen einzelnen Werten. Die Datei beginnt mit einer Kommentarzeile, die die Versionsnummer der TSP-Unit und die letzte Rechenzeit enthält. Das erste relevante Datum ist die Anzahl der Städte, darauf folgt die Art der Entfernungsberechnung (0: aus Karte, 1: symmetrisch, 2: asymmetrisch) und die Entfernungstabelle selbst. Ist zum Zeitpunkt des Speicherns keine Tabelle vorhanden, so wird sie aus der Karte generiert. Als nächstes kommen der vorherige und der aktuelle Weg, jeweils durch eine '-1' als Endekennung abgeschlossen, wobei in den vorausgehenden Kommentarzeilen auch die Längen angegeben sind. Den Abschluß bilden die Koordinaten der Städte.

  11. Laden

    Beim Laden wird eine Plausibilitätskontrolle der Daten vorgenommen und evtl. eine Fehlermeldung ausgegeben.

  12. Ende

    Hat die gleiche Wirkung wie der Schließknopf in der Titelleiste.


Implementierung

Die Programme sind in Turbo Pascal 4.0 geschrieben, laufen aber natürlich auch auf späteren Fassungen, insbesondere auf der unter http://community.borland.com/museum/ kostenlos erhältlichen Version 5.5 Free Pascal 2.6 geschrieben, kostenlos erhältlich unter http://www.freepascal.org. Sie sind in einem Drei-Schicht-System verwirklicht: Auf der untersten Ebene stellen die Units MAUS und GRAFIK problemunabhängige Routinen zur Verfügung, auf denen die Unit TSP aufbaut. Diese enthält die problemspezifischen Routinen und Datenstrukturen sowie die Benutzeroberfläche. Die oberste Schicht besteht schließlich aus den Lösungsalgorithmen, deren Realisierungen durch die Auslagerung insbesondere der Oberfläche ohne Verlust an Bedienungsfreundlichkeit kurz und übersichtlich gehalten werden können.

Die Listings der Units sind in Anhang B abgedruckt (s. auch "Sourcen der Units") und enthalten zu jeder Prozedur/Funktion einen Kommentar über die Anwendung, während hier nur die grundlegenden Strukturen und die am häufigsten benutzten Routinen erläutert werden.


Unit MAUS

Die Unit MAUS stellt ihrem Namen entsprechend Routinen für die Mausbenutzung zur Verfügung. Die wichtigsten sind:


Unit GRAFIK

Neben elementaren Grafikoperationen enthält diese Unit insbesondere Routinen zur Ausgabe von Text, zur Verwaltung von Menüs und zur Umrechnung verschiedener Koordinatensysteme.

Textausgabe

Menüverwaltung

Die Befehle zum Einrichten von Menüs legen jeweils eine Variable vom Typ MENU_DESC (descriptor)

   7: type menu_desc=record
   8:                 typ:(hor0,ver0,rec0,rec1);
   9:                 anzahl,anzahl2:word;
  10:                 x1,y1,x2,y2,abstand,abstand2:integer;
  11:                end;
an, die zusammen mit einem Koordinatenpaar (x,y) (üblicherweise die Position des Mauszeigers) der Funktion CHKMENU übergeben wird. Diese liefert dann die Nummer des zugehörigen Menüpunktes zurück.

Koordinatensysteme

Die Unit GRAFIK verwaltet drei verschiedene Koordinatensysteme: Das Mauskoordinatensystem umfaßt den ganzen Bildschirm mit dem Ursprung in der linken oberen Ecke und Werten entsprechend der physikalischen Auflösung (z. B. 640x480 für VGA-High). Mit dem Turbo Pascal-Befehl VIEWPORT oder der Prozedur SETWINDOW kann ein rechteckiger Bereich des Bildschirms ausgewählt werden, der Ursprung der Viewport-Koordinaten ist dann in der linken oberen Ecke dieses Bereiches, ansonsten entsprechen sie den Mauskoordinaten. Schließlich kann noch ein neues Koordinatensystem in einem Viewport angelegt werden, wobei der Ursprung der gleiche bleibt, aber die maximalen Werte frei wählbar sind.

Mit den Funktionen XV, YV, VX, VY, MX, MY, XM und YM können die Koordinaten der einzelnen Systeme ineinander umgerechnet werden, Details sind dem Listing in Anhang B.2 zu entnehmen.


Unit TSP

Wie bereits erwähnt enthält diese Unit (s. auch "Sourcen der Units") die problemspezifischen Elemente sowie die Benutzeroberfläche. Sie ist auflösungsunabhängig programmiert und läuft daher prinzipiell auf allen von Turbo Pascal unterstützten Grafikkarten, allerdings ist nur der VGA-Treiber fest eingebunden, während die der anderen Standards beim Start nachgeladen werden müssen. Außerdem ist die Darstellung für eine Palette mit mindestens 16 Farben optimiert.

Globale Deklarationen

  1. Konstanten

       7: const version=3.10;                 (* Versionsnummer *)
       8:       maxstadt=75;                  (* max. Anzahl v. Staedten *)
       9:       maxstadtquad=5625;            (* maxstadt^2 *)
      10:       maxentfernung=maxlongint;     (* max. Entfernung *)
      11:       maxstrecke=28633115;          (* max. Entfernung(+1) zw. zwei Staedten,
      12:                                        maxlongint/maxstadt *)
      13:       maxx=1240; maxy=999;          (* max. Koord. f. Karte *)
      14:       maxzufall=1599;               (* max. Entfernung(/1000) bei zufaelliger
      15:                                        Erstellung v. entftab *)
      16:       maxverfahren=40;              (* max. Anzahl v. Loesungsverfahren *)
    

  2. Variablentypen

      18: type stadt=record                   (* Stadtkoord. in Karte *)
      19:             x,y:longint;
      20:            end;
      21:      stadtnr=0..maxstadt;           (* Nr. von Staedten *)
      22:      entfernung=longint;            (* Entfernungen zw. Staedten *)
      23:      entfmatrix=array [1..maxstadt,1..maxstadt] of entfernung;
      24:                                     (* Entfernungsmatrix *)
      25:      entftyp=(kart,symm,asymm);     (* Art der Entfernungsbestimmung
      26:                                        kart: aus Karte, symm: zufaellig
      27:                                        symmetrisch, asymm: zufaellig asymm. *)
      28:      weg=string;                    (* Wege werden in Strings gespeichert *)
      29:      wegtypmenge=set of byte;       (* Byte-Menge fuer Wegtypen,
      30:                                        s. function wegtyp *)
    

  3. Globale Variablen

      32: var stadtkarte:array [1..maxstadt] of stadt;   (* Koord. der Staedte *)
      33:     entftab:entfmatrix;             (* Entfernungstabelle *)
      34:     entftabtyp:entftyp;             (* Art der Entfernungsbestimmung *)
      35:     vorher,aktuell:weg;             (* vorheriger u. aktueller Weg *)
      36:     stadtanzahl:stadtnr;            (* Anzahl Staedte *)
      37:     verfahren:byte;                 (* ausgewaehltes Loesungsverfahren *)
      38:     verfanzahl:byte;                (* Anzahl Loesungsverfahren *)
      39:     verfwegtypen:array [1..maxverfahren] of wegtypmenge;
      40:                                     (* Wegtypmengen der Verfahren *)
      41:     verftext:array [1..maxverfahren] of string[100]; (* Menuetexte/Titel d.
      42:                                        Verf., s. procedure verfahren_waehlen *)
      43:     verfformat:record               (* Format des Menues zur Verfahrenswahl *)
      44:                 x,y:byte;           (* x: Spalten, y: Zeilen *)
      45:                end;
      46:     startpunktwahl:boolean;         (* true: automatische Startpunktwahl *)
      47:     oben,unten,rechts:integer;      (* Position der Trennlinien zw. Menues und
      48:                                        Karte, links=0 *)
      49:     leiste,button,karte:menu_desc;  (* Menue-Descriptoren *)
    

Wichtige Prozeduren und Funktionen

Aufgeführt sind die Funktionen, die nicht nur intern, sondern auch in den Lösungsprogrammen verwendet werden.

Grundstruktur von TSP-Programmen

Ein Programm, das die Unit TSP benutzt, muß zuerst mit TSPINIT eine Initialisierung samt Bildschirmaufbau vornehmen. War dies erfolgreich, so wird in einer Schleife solange die Funktion TSPMENUE aufgerufen, bis diese den Wert false annimmt, was bedeutet, daß der Menüpunkt 'Ende' bzw. der Schließknopf angewählt wurde. TSPMENUE=true besagt hingegen, daß die Berechnung gestartet werden soll, das Ergebnis wird an die Variable AKTUELL übergeben. Für Programme mit nur einem Algorithmus ergibt sich daher folgende Struktur:

   1: program beispiel;
   2: uses graph,tsp;
         ...
   3: begin
   4:  if tspinit('TSP: Beispiel','Berechnen') then
   5:   while tspmenue([0..255]) do begin
         ...
   6:   end;
   7:  closegraph;
   8: end.

Bei mehreren Algorithmen müssen den Variablen VERFANZAHL, VERFWEGTYPEN, VERFTEXT, ... vor dem Aufruf von TSPINIT entsprechende Werte zugewiesen werden und in der Hauptschleife im Falle von TSPMENUE=true die Inhalte von VERFAHREN und STARTPUNKTWAHL ausgewertet werden, wie dies im Programmlisting von TSP_ALG (Anh. B.4) zu sehen ist.


Hilfsprogramme und TSP_ALG


TSP_PROT

Das Programm TSP_PROT erstellt aus den Dateien einer Serienberechnung Protokolle, wie sie in Anhang A zu finden sind. Die Angabe der Seriennamen erfolgt dabei in der gleichen Weise wie beim Menüpunkt 'Serie'. Falls der Name der Protokolldatei keine Namenserweiterung enthält, wird '.TPR' ergänzt.


KURZPROT

KURZPROT schreibt eine Kurzform existierender Serienprotokolle, bestehend aus den zusammenfassenden Zeilen an deren Ende, in eigene Dateien. Das Ergebnis sind Tabellen der in Kapitel 4 und 5 abgedruckten Form. Durch Verwendung von Jokerzeichen ('*', '?') können mehrere Protokolle bearbeitet werden, wobei die Ergebnisse unter dem gleichen Namen, aber mit einer geänderten einzugebenden Namenserweiterung, abgespeichert werden. Außerdem ist eine Konvertierung der Zeilenumbrüche ins Unix-Format (Linefeed (#10) statt Carriage Return (#13) und Linefeed (#10)) sowie das Einfassen der gesamten Tabelle in eine 'Verbatim'-Umgebung ('\begin{verbatim}' am Anfang und '\end{verbatim}' am Ende), was bei der Einbindung in ein LaTeX-Dokument diesen Abschnitt von der Formatierung ausnimmt und in einem nichtproportionalen Zeichensatz anzeigt, möglich. Mit der Eingabetaste lassen sich die in den Klammern vorgegebenen Werte, bei (n/j)-Angaben jeweils der erste Wert in der Klammer, übernehmen.


PAS_FORM

PAS_FORM dient zur formatierten Ausgabe von Pascal-Quelltexten und anderen Dateien mit einer einzugebenden Zeilenlänge, wobei jede Zeile mit einer Nummer versehen werden kann. Wie bei KURZPROT ist es durch die Verwendung von Jokerzeichen möglich, mehrere Dateien zu bearbeiten, das Speichern erfolgt wieder mit einer geänderten Namenserweiterung. Auch die Konvertierung der Zeilenumbrüche sowie das Einfügen von 'Verbatim'-Umgebungen stehen zur Verfügung, zusätzlich können DOS-Umlaute an die Latin1-Zeichentabelle (Windows/Unix) angepaßt werden.


TSP_ALG

In TSP_ALG sind die Einzelprogramme der folgenden Kapitel in einem Programm zusammengefaßt, das Listing des Hauptprogramms befindet sich in Anhang B.4 (Abb. 2.2: Verfahrensauswahl bei TSP_ALG).


Thomas Klein

Zurück