... auch unter den deutschen Bezeichnungen: Rundreiseproblem, Vertreterproblem oder der englischen Abkürzung TSP vielfach behandelt. Warum finden Sie es unter "Zeit und Geld"?
Weil in unserer sozial(istisch)en Marktwirtschaft Handlungreisende nur an Zeit und Geld, aber nicht an Altmodisches wie Qualität oder Ehrlichkeit denken (müssen?).
Gegeben sei eine Anzahl N von Städten sowie die Entfernungen zwischen den Städten. Der Reisende soll jede Stadt (mit Ausnahme der Heimatstadt, in der er starte und in der er wieder ankommen soll) genau einmal besuchen, der Weg soll minimiert werden. Nimmt man die bloßen Abstände, dann ist die Matrix der Entfernungen/Aufwände symmetrisch. Diese Spezialisierung ist aber nicht notwendig. Das Problem ist auch mit asymmetrischen Kostenfunktionen formulier- und lösbar. (Beispiel: der Wassertransport von Dresden nach Hamburg ist einsehbar billiger als der von Hamburg nach Dresden.)
| 499! = 24402736519822201374024775708460938525071486856063856843848271767716907463077639952 10992895004406563726027232954296407168326757444156354400961570410318658570955815143 87866120754592171817254085834909576484982545268861134034654153892212560462090528843 77575789315095542997269887355620752885480676547307949427729557569908769791910750759 80846482122542653968655491431092619954405562029122162376747419062032712648865974059 12779325782331794953914417585385774256356014053034901553682143924878078864507284521 04698917002598371430024974139231362832507181133868476260177124984937831282535513089 63773013187695903550721788011490477880671596952727889810626124647498132890097649330 15189347172414927585036840091873938596204452794390519438189043564666351386916301710 46656415256400468052538157966849034240124154292819589122322552582919024744598266803 39104727701885771184037454867590346029172715141656711560317470865537777360240799764 76940430293521089081532707196834886096025787662779376327897493931763500901385273067 63501109562572800000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000 |
Das sind 1132 Stellen. Würde die Berechnung und Bewertung einer kompletten Weglänge 1µs dauern, was eine sicher noch recht zukunftssichere Annahme ist, so bräuchte man ca. 499!/(1000*1000*60*60*24*365) Jahre, um alle möglichen Wege zu prüfen. Das sind dann ca. 101118 Jahre. Könnte schon sein, daß da einer inzwischen die Lust an der Rundreise verliert.
Das Problem soll bereits 1831 in Deutschland unter dem - natürlich nachträglich übersetzten - Titel: "Who is a Travelling Salesman and What He Should Do to Make His Enterprise Prosper" formuliert worden sein.
Es gibt mehrere klassische Lösungs- (bzw. Näherungs-)verfahren, man hat es insbesondere in den letzten Jahren mittels Neuronaler Netze und Genetischer Algorithmen versucht. Diese sind, ebenso wie klassische Näherungsverfahren, aus Prinzip nicht geeignet, das absolute Minimum des Weges zu finden.
Literatur zum benutzten Algorithmus:
Graphen, Algorithmen, Programme; H. Walther, G. Nägler; VEB Fachbuchverlag Leipzig 1987
Die Programmbeschreibung soll ausnahmsweise nicht mit dem Programmkern beginnen, sondern mit dem Drumrum, weil er, der Kern, sonst schwer zu erklären und schwer zu verstehen wäre.
Bevor die Sache richtig losgehen kann, braucht man eine ganze Reihe von Variablen.
Wir stellen uns Zahl Städte vor, die in einem cartesischen Koordinatensystem die Koordinatenwerte StadtX() und StadtY() besitzen, Arrays, weil es ja viele sind. Die hier namenlosen Städte, die durch ihre Stellung in den Koordinatenarrays gekennzeichnet sind, werden in einer Reihenfolge Reihe() besucht. Als Rechenhilfe berechnen wir hier eine Abstandsmatrix Entf(,), an deren Stelle könnten natürlich echte Straßen- und/oder Bahn-Kilometer eingetragen werden. Schließlich steht Weg überraschenderweise für die Länge der Rundreise.
| Option Explicit Dim Zahl As Integer Dim StadtX(1000) As Long, StadtY(1000) As Long Dim Reihe(1000) As Integer Dim Entf(1000, 1000) As Single Dim Weg As Single, altWeg As Single |
Es folgen einige unwichtige, aber notwendige Kleinaktivitäten, die keiner weiteren Erörterung bedürfen.
| Private Sub Command2_Click() 'Ende-Button End End SubPrivate Sub HScroll1_Change() 'Wahl der Städtezahl Zahl = HScroll1.Value End SubLabel1.Caption = Zahl & " Städte" Sub Form_Load() 'Anfangswerte setzen Randomize End SubZahl = 50 HScroll1.Value = Zahl Label1.Caption = Zahl & "Städte" |
Dann zwei Routinen, die wir brauchen, um den Fortschritt erkennbar zu machen. Sie nutzen eine Picture-Box Picture1.
Wichtig: Während man die Städte getrost in Reihenfolge ihrer Nummern malen kann, müssen die Wege in der Reihenfolge gemalt werden, die gerade in Reihe() steht und bei jeder Malerei anders sein wird.
| Sub Malestädte() Dim i% Picture1.Cls For i = 1 To Zahl Picture1.DrawWidth = 3 Picture1.PSet (StadtX(i), StadtY(i)), QBColor(0) Next End SubPicture1.DrawWidth = 1 Sub Malewege() Dim i%, j% Malestädte For i = 1 To Zahl j = i + 1 If j> Zahl Then j = 1 Picture1.Line (StadtX(Reihe(i)), StadtY(Reihe(i)))-(StadtX(Reihe(j)), StadtY(Reihe(j))), QBColor(1) Next End Sub |
Jetzt kommen wir zur Sache, der Button Command1 soll alles in Gang setzen:
| Private Sub Command1_Click() Dim i%, j%, k%, Start%, MalX% Dim test%, ok As Boolean Dim Rand% 'Generiere Städtemuster Rand = Int(Picture1.ScaleWidth / 50) For i = 1 To Zahl StadtX(i) = Rand + Int((Picture1.ScaleWidth - 2 * Rand) * Rnd) StadtY(i) = Rand + Int((Picture1.ScaleHeight - 2 * Rand) * Rnd) Next 'Berechne Abstandsmatrix For i = 1 To Zahl For j = 1 To Zahl Entf(i, j) = Sqr((StadtX(i) - StadtX(j)) ^ 2 + (StadtY(i) - StadtY(j)) ^ 2) / 10000# Next Next 'Darstellung der Städte Malestädte 'generiere Startreihenfolge For j = 1 To Zahl Do Reihe(j) = 0 ok = True test = Int(Zahl * Rnd + 1) For k = 1 To j If Reihe(k) = test Then ok = False Next Loop Until ok = True Reihe(j) = test Next 'verringere Reiseweg Weg = 10000 Do While Weg <> altWeg altWeg = Weg For i = 1 To 10 TSklassic Zahl, Weg Next Malewege DoEvents Loop End Sub |
Soweit alles klar, bis auf die offenbar gar nicht so unwichtige Prozedur, deren Aufruf " TSklassic Zahl, Weg" heißt. In ihr wird der Weg - hoffentlich - verringert.
Kurzerklärung: Wenn man eine ausgewürfelte Reihenfolge der Städte als Kette sieht, wird geprüft, ob durch Austausch der Verbindungsstücke zwischen jeweils zwei Nachbarn eine Verbesserung (Verringerung von kst) eintritt und die beste realisiert. Eine Verbesserung tritt immer dann ein, wenn sich kreuzende Wege beseitigt werden. Very sophisticated.
Wir warten jeweils 10 Verkürzungen ab, bis eine neue Darstellung der Gesamtroute erfolgt.
Es folgt der eigentliche Programmkern:
| Sub TSklassic(ByVal n%, kst As Single) Dim einsparung!, diff! 'Wege Dim j%, k%, l% 'Laufindices Dim u%, v%, x%, y%, z%, kend%, js%, ks%, hh%, kw% einsparung = 0 For j = 1 To n - 2 u = Reihe(j) v = Reihe(j + 1) If j = 1 Then kend = n - 1 Else kend = n For k = j + 2 To kend x = Reihe(k) If k < n Then y = Reihe(k + 1) Else y = Reihe(1) diff = Entf(u, v) + Entf(x, y) - Entf(u, x) - Entf(v, y) If diff > einsparung Then einsparung = diff js = j ks = k End If Next Next If einsparung > 0 Then For k = 1 To (ks - js) \ 2 hh = Reihe(k + js) Reihe(k + js) = Reihe(ks - k + 1) Reihe(ks - k + 1) = hh Next kst = kst - einsparung End If End Sub |
Das folgende Bild zeigt das Ergebnis einer Berechnung für 500 Städte.
Man erkennt, daß es einzelne Punkte gibt, deren Einordnung zwischen anderen Städten zur Verkürzung der Route führen würde. Man kann ohne großen Aufwand einen "Nachbrenner" schreiben, der für jeden der vorhanden Orte prüft, ob er sich zwischen einem der vorhandenen Punktepaare mit Gewinn einsortieren läßt. Das führt zu einer deutlichen Verbesserung. Alle mit dem Auge erkennbaren Fehler sind damit zu beseitigen. Diese Routine ergänzen Sie bitte selbst!
Eine Garantie für den kürzesten Weg bietet auch diese Ergänzung - aus Prinzip - nicht!
Wer einmal sehen will, wie die Suche so funktioniert, dem sei mit einem Java-Applet geholfen, das den vorgestellten Algorithmus nutzt. Es sind bis zu 1000 Städte wählbar.
Viel Spaß!
