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.
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 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.
Die Unit MAUS 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 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 "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.
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 *)
Versionsnummer der TSP-Unit
Die maximale Städteanzahl von 75 ist durch die Turbo Pascal-Beschränkung von 64 KByte für den Variablenbereich bedingt. MAXSTADTQUAD=MAXSTADT² wird im Algorithmus von Prim zur Berechnung minimaler erzeugender Bäume benötigt.
Da für die Speicherung der Entfernungen longint-Variablen benutzt werden, ist der maximale Wert MAXENTFERNUNG gleich MAXLONGINT. MAXSTRECKE ist um eins größer als die maximal erlaubte Entfernung zwischen zwei Städten. Damit die Länge einer Tour MAXENTFERNUNG nicht überschreiten kann, hat die Konstante den Wert MAXENTFERNUNG/MAXSTADT.
Dies sind die Koordinaten der rechten unteren Ecke der Stadtkarte.
Die maximale Entfernung zwischen zwei Städten bei der zufälligen Erstellung der Entfernungstabelle ist MAXZUFALL*1000.
Maximale Anzahl der Lösungsverfahren in einem Programm
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 *)
Nimmt Koordinaten von Städten auf.
Städte werden von eins bis MAXSTADT durchnumeriert, der Wert null bedeutet eine Unterbrechung eines Weges (s. WEG).
Für Entfernungen werden Festkommawerte mit drei Nachkommastellen verwendet, die intern mit 1000 multipliziert in longint-Variablen gespeichert werden.
Entfernungsmatrix
Die Entfernungen zwischen Städten können aus der Lage der Städte in der Karte (kart) oder zufällig symmetrisch (symm) bzw. asymmetrisch (asymm) bestimmt werden.
Wege werden in Strings gespeichert, dabei nimmt jedes Zeichen die Nummer einer Stadt als ASCII-Wert auf, also z. B. '#1#2#3#1' für eine Tour mit dem Start-/Endpunkt 1. Mit #0 können Unterbrechungen eingefügt werden, '#1#2#3#1#0#4' besteht also aus der vorherigen Rundreise und dem isolierten Punkt 4. Die Verwendung von Strings bietet den Vorteil, daß mittels Zeichenkettenfunktionen wie INSERT oder COPY leicht größere Teile von Touren manipuliert werden können.
Wegtypmengen werden im allgemeinen benutzt, um zu definieren, mit welchem vorgegebenem Wegtyp (s. Programmbedienung) ein TSP-Algorithmus aufgerufen werden kann, beispielsweise [113] bei optimierenden Verfahren, die eine bestehende Rundreise als Vorgabe benötigen.
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 *)
Enthält die Koordinaten der Städte.
Tabelle der Entfernungen zwischen den Städten (Kostenmatrix)
Art der Entfernungsbestimmung
Vorheriger und aktueller Weg
Anzahl der Städte
Nummer des ausgewählten Lösungsverfahrens. Wurde kein Verfahren gewählt, so enthält die Variable den Wert null. Bei Programmen mit nur einem Verfahren ist sie ohne Bedeutung.
Anzahl der Lösungsverfahren. Ist der Wert kleiner als eins, so wird der Menüpunkt 'Verfahren' nicht angezeigt. Der Standardwert ist null.
VERFTEXT enthält für jedes Lösungsverfahren einen String im Format '*Menüeintrag|Titelleistentext'. 'Menüeintrag' ist der Text, der im Menü der Verfahrenswahl erscheint, 'Titelleistentext' wird nach der Auswahl dieses Verfahrens in der Titelleiste eingeblendet. Steht an der Stelle des '*' ein '+', so wird gefragt, ob eine automatische Startpunktwahl erfolgen soll.
Gibt an, wie viele Zeilen und Spalten das Menü zur Verfahrensauswahl haben soll. Vorgegeben sind VERFFORMAT.X=5 und VERFFORMAT.Y=8.
Erhält den Wert true, falls bei der Verfahrenswahl die automatische Startpunktwahl eingestellt wurde.
Positionen der Trennlinien zwischen Menüs und Karte in Abhängigkeit von der Bildschirmauflösung. Die linke Begrenzung hat den Wert 0.
Menüdeskriptoren der rechten Menüleiste, des Schließknopfes und der Stadtkarte.
Aufgeführt sind die Funktionen, die nicht nur intern, sondern auch in den Lösungsprogrammen verwendet werden.
procedure WEGTXT(w:weg;warten:boolean)
Gibt die Städte des Weges w im Textmodus aus. Falls warten=true ist, wird danach auf einen (Maus oder Tastatur-)Tastendruck gewartet. Diese Prozedur dient hauptsächlich zur Fehlersuche.
function WEGLAENGE(w:weg):entfernung
Berechnet die Länge von w.
procedure MENUE(abstand:integer;menu:string;
backcol,txtcol,trenncol:word;var desc:menu_desc)
Zeichnet ein horizontales Menü in der unteren Leiste, die Parameter entsprechen denen der HMENU-Prozedur.
procedure MELDUNG(s:string;hintergrund,schrift:word)
Gibt s in der Statusleiste mit den Farben hintergrund und schrift aus. Der Grafikcursor steht danach hinter dem letzten Zeichen, so daß weitere Zeichen angeschlossen werden können.
procedure LAENGE_AUS(w:weg)
Schreibt ,,Länge des aktuellen Weges: abcd.efg`` mit der Länge von w in die Statusleiste. Für den Grafikcursor gilt das bei MELDUNG Gesagte.
procedure START0, procedure START, procedure STOP
Startet und stoppt die Zeitmessung, bei START wird zusätzlich die Meldung ,,Lösung wird berechnet`` und bei Serienberechnungen der aktuelle Serienteil ausgegeben.
function ZEIT:real
Liefert die gestoppte Zeit.
procedure ZEIT_AUS(komma:boolean)
Gibt die gestoppte Zeit, evtl. mit einem vorangestellten Komma (komma=true), an der aktuellen Grafikposition aus. Normalerweise wird die Routine im Anschluß an LAENGE_AUS aufgerufen.
procedure ZEICHNE_KARTE(loeschen:boolean;farbe:word)
Zeichnet alle Städte mit der Farbe farbe in die Karte ein. Bei loeschen=true wird der Bereich vorher gelöscht.
procedure ZEICHNE_WEG(w:weg;loeschen:boolean;farbe:word)
Zeichnet w mit farbe in die Karte ein, evtl. wieder mit vorherigem Bildschirmlöschen.
procedure FARBSTADT(nr:stadtnr;farbe:word)
Trägt die Stadt nr mit der angegeben Farbe in die Karte ein.
procedure STARTSTADT(w:weg;farbe:word)
Wie FARBSTADT für die erste Stadt des Weges w.
procedure WEGKARTE(w:weg;loeschen:boolean;wegfarbe,kartenfarbe:word)
Kombination von ZEICHNE_WEG und ZEICHNE_KARTE
function STADTWAHL(button:byte):stadtnr
Wartet, bis die Maustaste button (bei 255 eine beliebige Maustaste) gedrückt wird, und bestimmt dann die dem Mauszeiger nächstgelegene Stadt.
procedure ZUFALLSWEG(var w:weg)
Weist w eine zufällig erzeugte Tour zu.
function TSPMENUE(wegtypen:wegtypmenge):boolean
Überwacht alle Menüpunkte und führt bei einem Aufruf die entsprechenden Reaktionen aus. Verlassen wird die Funktion nach dem Anklicken des Schließknopfes bzw. des Menüpunktes 'Ende' und anschließender Bestätigung, in diesem Fall ist der Funktionswert false, oder mit dem Menüpunkt zum Aufruf der Lösungsroutine (Funktionswert=true). Letzteres ist allerdings nur möglich, wenn der aktuelle Wegtyp in der Menge wegtypen enthalten ist, ansonsten wird eine Fehlermeldung in der Statusleiste ausgegeben.
function TSPINIT(titel,aufruf:string):boolean
Falls ein Maustreiber installiert ist, werden notwendige Initialisierungen vorgenommen und der Bildschirm gezeichnet. Die Titelleiste erhält den Inhalt titel, der Menüpunkt zum Aufruf der Lösungsroutine die Bezeichnung aufruf. War kein Maustreiber vorhanden, so wird die Routine mit einer entsprechenden Meldung und dem Funktionswert false abgebrochen, im Erfolgsfall ist der Rückgabewert true.
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.
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).