Abbildung 2.1: Benutzeroberfläche
Die Unit TSP stellt basierend auf den Units MOUSE 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.
Abbildung 2.1: Benutzeroberfläche
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):
Mit dem Schließknopf in der rechten oberen Ecke kann das Programm nach einer Sicherheitsabfrage beendet werden.
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.
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:
Löscht nach einer Sicherheitsabfrage alle Städte samt Weg und die Entfernungstabelle.
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.
Nach dem Anklicken der ersten und letzten Stadt werden alle potentiell zu löschenden Punkte eingefärbt und nach einer Sicherheitsabfrage entfernt.
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'.
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.
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.
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.
Ü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.
Gibt eine Hardcopy der Karte auf Epson- oder Hewlett-Packard-kompatiblen Druckern aus.
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.
Beim Laden wird eine Plausibilitätskontrolle der Daten vorgenommen und evtl. eine Fehlermeldung ausgegeben.
Hat die gleiche Wirkung wie der Schließknopf in der Titelleiste.
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. Sie sind in einem Drei-Schicht-System verwirklicht: Auf der untersten Ebene stellen die Units MOUSE 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 TP 4.0-Units bzw. TP 5.5-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.
Die Unit MOUSE ist eine modifizierte Fassung der Unit MAUS von Prof. H. Schupp und stellt ihrem Namen entsprechend Routinen für die Mausbenutzung zur Verfügung. Die wichtigsten sind:
procedure MAUSEINSATZ
Initialisierungsroutine, die den Mauseinsatz vorbereitet. War die Initialisierung erfolgreich, so wird die Variable MAUSOK:boolean auf true gesetzt, ansonsten, z. B. wenn kein DOS-Maustreiber vorhanden ist, behält sie den Wert false.
procedure ZEIGE_MAUS, procedure VERSTECKE_MAUS
Mit ZEIGE_MAUS und VERSTECKE_MAUS kann man die Darstellung des Mauszeigers ein- und ausschalten. Nach mehrfachem Verstecken muß zur Anzeige ZEIGE_MAUS wieder genauso oft aufgerufen werden. Dadurch wird der Einsatz in Unterprogrammen erleichtert.
procedure MAUSSTATUS
Die aktuellen Mauskoordinaten und der Status der Maustasten werden an die Integervariablen MAUSX, MAUSY und MAUS_STATUS übergeben. Die Koordinaten beziehen sich dabei immer auf den gesamten Bildschirm, von Turbo Pascal gesetzte 'Viewports' werden nicht berücksichtigt.
procedure WARTE_MAUS(status:byte)
Ruft solange MAUSSTATUS auf, bis MAUS_STATUS den Wert status annimmt, also die entsprechende Maustaste gedrückt bzw. losgelassen wird.
procedure WARTE, procedure WARTE0
Wartet auf eine Maustaste oder einen Tastendruck, WARTE0 führt vorher noch WARTE_MAUS(0) aus (keine Maustaste gedrückt). Ist MAUSOK=false, dann wird nur die Tastatur abgefragt.
Neben elementaren Grafikoperationen enthält diese Unit insbesondere Routinen zur Ausgabe von Text, zur Verwaltung von Menüs und zur Umrechnung verschiedener Koordinatensysteme.
procedure SETTEXTNORM(groesse:word)
Setzt die Einstellungen für den Textstil auf Standardwerte und bestimmt die Textgröße (1: normal, 2: doppelte Größe, ...).
procedure OUTINTXY(x,y:integer;num:longint;breite:byte),
procedure OUTREALXY(x,y:integer;num:real;breite,nachkomma:byte)
Gibt an der Stelle (x,y) den (Long-)Integer- oder Real-Wert num rechtsbündig aus. breite und nachkomma geben die Anzahl der gesamten Stellen bzw. die für den Nachkommateil an (vgl. Formatangabe beim WRITE-Befehl).
procedure OUTSTRXY(x,y:integer;s:string;abstand:integer)
Der String s wird an der Position (x,y) ausgegeben. Enthält er das Zeichen '~', so erfolgt an dieser Stelle ein Zeilenumbruch, wobei die nächste Zeile um abstand nach unten versetzt wird.
procedure OUTINT(num:longint;breite:byte),
procedure OUTREAL(num:real;breite,nachkomma:byte),
procedure OUTSTR(s:string;abstand:integer)
Wie die entsprechenden ...XY-Befehle, die Ausgabe erfolgt aber an der aktuellen Position des Grafikcursors.
procedure TEXTBAR(xoben,yoben,xunten,yunten:integer;s:string; groesse,fill,backcol,txtcol:word)
Zeichnet einen Balken mit den angegebenen Eckkoordinaten und gibt darin den String s mit der Textgröße groesse und der Farbe textcol aus. Der Balken wird mit dem Turbo Pascal-Füllmuster fill in der Farbe backcol ausgefüllt bzw. für fill=0 in dieser Farbe umrandet.
procedure SETTEXTBOX(x1,y1,x2,y2,abstand:integer; groesse,fill,backcol,txtcol:word)
Definiert ein Rechteck für nachfolgende Textausgaben, die Parameter entsprechen denen von TEXTBAR. abstand ist der Zeilenabstand in Pixeln, für negative Werte wird er auf Zeichenhöhe+2 gesetzt (exakt: Höhe des Zeichens '*'+2).
procedure TEXTBOX
Zeichnet eine mit SETTEXTBOX definierte Textbox (entspricht einem CLRSCR im Textmodus).
procedure BOXCR
Zeilenumbruch in einer Textbox (analog zu WRITELN)
procedure BOXOUT(s:string;abbruch:boolean)
Gibt s in einer Textbox aus. Beim Überschreiten des rechten Randes erfolgt ein Zeilenumbruch, am unteren Rand wird auf einen (Maus- oder Tastatur-)Tastendruck gewartet und nach einem TEXTBOX-Aufruf die Ausgabe fortgesetzt. Ist abbruch=true, so kann an dieser Stelle die Ausgabe mit der rechten Maustaste oder den Tasten 'q', 'x' oder 'e' abgebrochen werden, wobei BOXEXIT:boolean den Wert true erhält.
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.
procedure RECT(x1,y1,x2,y2:integer;var desc:menu_desc)
Definiert einen rechteckigen Bereich.
procedure CLOSEBUTTON(x1,y1,x2,y2:integer;backcol,linecol:word; var desc:menu_desc)
Zeichnet einen Schließknopf mit den Farben backcol (Hintergrund) und linecol (Linien).
procedure HMENU(xoben,yoben,xunten,yunten,abstand:integer;menu:string; groesse,fill,backcol,textcol,trenncol:word;var desc:menu_desc)
Legt ein horizontales Menü mit den angegebenen Koordinaten an, das durch den String menu definiert wird. Dieser besteht aus den einzelnen Menüpunkten, jeweils durch '|' getrennt und kann '~'-Zeichen zum Zeilenumbruch enthalten. Der Abstand zwischen den einzelnen Punkten beträgt abstand, für abstand<0 -Menübreite/abstand. trenncol ist die Farbe der Trennungsstriche zwischen den einzelnen Bereichen, die restlichen Parameter entsprechen denen der TEXTBAR-Prozedur.
procedure VMENU(xoben,yoben,xunten,yunten,abstand:integer;menu:string; groesse,fill,backcol,textcol,trenncol:word;var desc:menu_desc)
Analog zu HMENU wird ein vertikales Menü angelegt, für abstand<0 beträgt der Abstand zwischen den Menüpunkten -Menühöhe/abstand.
procedure RMENU(xoben,yoben,xunten,yunten,xabstand,yabstand:integer; fill,backcol,textcol,trenncol:word;var desc:menu_desc)
Definiert ein rechteckiges Menü. Die Menüeinträge werden mit dem folgenden Befehl gezeichnet.
procedure RMENUENTRY(nr:word;menu:string;groesse,textcol:word; var desc:menu_desc)
Schreibt menu als nr. Eintrag in das durch desc beschriebene Menü.
function CHKMENU(x,y:integer;desc:menu_desc):word
Liefert die Nummer des zu (x,y) gehörenden Menüpunktes aus dem durch desc beschriebenen Menü. Liegt (x,y) außerhalb des Menüs, so erhält man den Wert null.
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.
procedure SETWINDOW(x1,y1,x2,y2:integer;xmax,ymax:longint)
Definiert ein neues Koordinatensystem in dem Bildschirmbereich (x1...x2, y1...y2) mit dem Ursprung bei (x1,y1) und dem Koordinatenpaar (xmax,ymax) bei (x2,y2).
procedure WINDOWON, procedure WINDOWOFF
WINDOWON aktiviert den mit SETWINDOW definierten Bereich als Viewport und schaltet das Clipping ein, d. h. es werden keine Punkte außerhalb des Viewports gezeichnet. WINDOWOFF schaltet den Viewport wieder ab.
Wie bereits erwähnt enthält diese Unit (s. auch TP4.0-Units bzw. TP 5.5-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.
...
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,noendlos;
...
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.
Die Unit NOENDLOS bewirkt, daß ein Programm jederzeit mit der 'Druck'-Taste abgebrochen werden kann und darf ersatzlos weggelassen werden.
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 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 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.
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).
