Rundreiseproblem oder Problem des Handlungsreisenden - The Traveling Sales-Mans Problem history menue Letztmalig dran rumgefummelt: 11.06.15 21:25:26

Das Rundreiseproblem ist so einfach wie genial und in der Ausführung extrem verblüffend: gesucht ist die kürzeste Verbindung zwischen einer gegebenen Menge von Städten, wobei jede Stadt genau einmal passiert werden muss und zum Ausgangspunkt zurückgekehrt wird. Das war's auch schon - und nun viel Vergnügen ;-)
1. Problembeschreibung
2. Hintergründe und Zusammenhänge - Einordnung in Klassen
3. Lösungsalgorithmen
4. Programmvorschläge
5. Zusammenfassung
6. Weiterführende Literatur
7. Linkliste zum Thema
8. Verwandte Themen

Probleme & Problemlösungsverfahren

Logo zum Rundreiseproblem

Informatik-Profi-Wissen

Quellen:

Lösbarkeit und Problemlösungsstrategien

Graphentheorie ist auch hierbei die Basis

der "Worst-Case" liegt hier sicher nicht in der Komplexität zum Aufwand für den Lösungsalgorithmus - er ist hier allein in der Mächtigkeit des Problems zu suchen
Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer


1. Problembeschreibung history menue scroll up

Das Rundreiseproblem gehört zu den klassischen, für große Mächtigkeiten, nicht lösbaren Problemen.
Zu ermitteln ist die kürzeste Trassierung aller gegeben Knoten durch einen Kreis, wobei jede Strecke möglichst nur einmal zu befahren ist. Einproblem, welches für Logistikunternehmen, Postzusteller sowie Schiffahrtsrouten (NEIN - das schreib' ich schon aus Prinzip nicht mit drei "f"!) ganz real ist.
Bereits für einen kleine Anzahl n gegebener Knoten in bekanntem Abstand m ergibt sich eine zu untersuchende Mächtigkeit, welche in realem Antwortzeitverhalten nicht erreichbar ist. Interessant dabei ist, dass bereits bei der Hälfte der untersuchten Fälle zumindest für bestimmte Strukturen eine Toleranzschwelle von 3 % erreicht wird - mit anderen Worten: bis auf 3 % Ungewissheit habe ich die Minimallösung.

Ausgangspunkt für das Rundreiseproblem

eine mögliche Lösung

Graphenstruktur für Sachsen

Ausgangspunkt für das Rundreiseproblem

Download als CorelDraw 11-0-Datei

 

eine mögliche Lösung

 

Graphenstruktur für Sachsen

exakte Lösung unmöglich - es existieren 45 651 133 223 206 551 617 074 619 Möglichkeiten

größtes bisher gelöstes Rundreiseproblem

reale Problemlösungsversuche scheitern an den Dimensionen der verfügbaren Datentypen - für die Mehrheit aller Fälle ist die Lösungsmenge für eine "nicht große" Anzahl von Städten nicht in realer Lebenserwartungszeit möglich
wir rechnen dies einmal für n = 50 gegebene Städte durch (die obige Karte von Sachsen könnte also durchaus ein realer Fall sein), wobei Kreuzungen von Straßen nicht zugelassen sind, oder als separater Knoten existieren sollen:
  • mathematisch nachgewiesen ist, dass, wenn jeder Knoten mit mindestens zwei Kanten verbunden ist, mindestens n/2! Möglichkeiten zur Verbindung der Knoten (und damit der Trassierung) existieren
  • 50 : 2 = 25 (bis hierher ist das nicht kompliziert
  • 25! ermittelt uns der Taschenrechner - und das ist auch noch nicht schwer - aber: das sind 15.511.210.043.330.985.984.000.000 Möglichkeiten (und da sind die letzten 6 Stellen gerundet - unser Ergebnis ist also um mindestens 1.000.000 ungenau - aber sei's drum - weiter:
  • alle Bundesbürger (81.000.000) rechnen mit - jeder übernimmt einen Teil der möglichen Lösungen und es sei abgestimmt, dass keiner die selben Fälle untersucht - dann bleiben für jeden Bundesbürger: 191.496.420.288.036.864  Fälle zum recherchieren
  • wir nehmen weiterhin an, dass jeder Bundesbürger einen Computer benutzt, dieser fehlerfrei programmiert ist (welch eine Illusion!) und der pro Sekunde einen Fall fehlerfrei ermitteln kann:
  • dann hat eine Minute 60 Sekunden, eine Stunde 3.600 Sekunden und ein Tag 86.400 - für ein Durchschnittsjahr von 365 Tagen  erhalten wir folgerichtig 31.536.000 und wissen somit, wie viele Fälle jeder Bundesbürger pro Jahr untersuchen kann ;-)
  • nun brauchen wir ja nur die Anzahl der Fälle, welche jedem zukommen durch die Anzahl seiner Untersuchungszahlen pro Jahr zu dividieren und erhalten: 191.496.420.288.036.864 : 31.536.000
  • und - krawumm: jeder untersucht 6.072.311.652,969.205.479.452.054.794.520.5 Jahre lang lassen wir mal die Nachkommastellen weg - so sind das: 6.072.311.652
  • wir schätzen das Alter der Erde heute auf ca. 4.000.000.000 Jahre
  • also: wenn alle Bundesbürger pro Sekunde einen Fall untersuchen, benötigen wir für 50 Städte zur Rundreiseanalyse 1,518077913 - also rund 1,5 mal so lange, wie die Erde jetzt schon existiert


2. Hintergründe, Zusammenhänge - Einordnung in Klassen history menue scroll up

Es ist interessant, zu ermitteln, unter welchen Bedingungen es überhaut Traversierungen im Sinne der Rundreise geben kann und welchen Einfluss neben der Anordnung die Anzahl sowie Lage der Kanten gegebenen Kanten haben. Im folgenden sind dazu Fallbeispiele aufgestellt, an welchen man die Gestzmäßigkeiten selbst erkunden kann - interessant ist dabei die Idee, dass man landläufig davon ausgeht, dass es bei hoher Anzahl von Knoten zwangsläufig mindestens eine Umfahrung geben muss - muss es nicht ;-)
Lösungsverfahren und -möglichkeiten sind abhängig von:
  • der Anzahl der Knotenpunkte
  • der Lage der Knotenpunkte untereinander
  • der Anzahl sowie Lage der Kanten

nicht im Sinne des Rundreisens "optimal" gelöst - aber als Lösungsmenge Aufgabe prinzipiell erfüllt ;-)

1 bis 4 Knotenpunkte planar trassiert

das sind zwar Aufgaben, aber keine Probleme - es gibt einfach keine Alternativen ;-)

ab vier Knoten gibt es Varianten - dabei auch unechte, da mindestens eine Strecke doppelt befahren werden muse

ab vier Knoten gibt es Varianten - dabei auch unechte, da mindestens eine Strecke doppelt befahren werden muse

5 Knotenpunkte planar trassiert

bei 5 Knoten entscheidet die Lage

5 Knoten - einer davon eingeschlossen - jedoch planar verbunden

5 Knoten - einer davon eingeschlossen - jedoch planar verbunden

7 Knotenpunkte planar trassiert

Rundreiseproblem mit 7 Städten in gegebener Lage

Rundreiseproblem mit 7 Städten in anderer gegebener Lage

Rundreiseproblem mit 7 Städten in anderer gegebener Lage

8 Knotenpunkte planar trassiert

Rundreiseproblem mit 8 Städten in gegebener Lage

Rundreiseproblem mit 8 Städten in anderer gegebener Lage

... wenn ich diese Aufgabe einsetze, dann sollte man die Lösungen oben nicht einsehen können ;-)

bei einem innen liegenden Knoten auch mit drei anbindenden Kanten ist keine Rundreise möglich

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

   
Erhöhung der innen liegenden Kanten um genau eins

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erste sowie einzige Möglichkeit der Traversierung

wir spendieren eine weitere Innenkante

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

 

 
... und fügen nochmals an zum vollständigen planaren Graphen

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

erstmals gibt es Trassierungsmöglichkeiten im Sinne des Rundreiseproblems

Lageanalyse für vollständige und unvollständige planare Graphen als Basis des Rundreiseproblems

Anordnung der Knoten auf einem Ring - vollständig planar trassiert

Anordnung der Knoten eingeschlossen in einem Ring - unvollständig planar trassiert

Anordnung der Knoten eingeschlossen in einem Ring - vollständig planar trassiert

Anordnung der Knoten eingeschlossen in einem Ring - vollständig planar trassiert

hier zur Übersicht zu Block D als EXCEL-Datei

Rundreiseproblem mit 6 Städten in anderer gegebener Lage


3. Lösungsalgotihmen history menue scroll up
Der Laie vor dieses Problem gestellt kann nur probieren, vom Ausgangspunkt jeweils die kürzeste Verbindung zum nächsten Knoten (also der nächsten Stadt) zu suchen und diesen dann abzufahren. Dort angekommen wiederholt er dieses Spiel in der Hoffnung, dass dies klappt. Nun kann man aber feststellen bzw. vorher berechnen, ab wann es evtl. gar keine richtige Lösung mehr gibt - das entfällt beim Probieren.

 


4. Programmvorschläge history menue scroll up

Das erste und vorläufig einzige Beispiel stellt ein PASCAL-Programm vor, welches die Unentscheidbarkeit immerhin bis 64 KByte Zeichen hinauszögert, Lösungen im oben genanten Sinne kann es für nicht unentscheidbare Kombinationen keine geben - auch der größte Computerspeicher ist endlich in seinem Speichervolumen :-(
 


5. Zusammenfassung history menue scroll up

Das Rundreiseproblem scheitert für die wohl meisten Fälle nicht an seiner Komplexität, sondern an seiner Mächtigkeit - eben schon für sehr kleine Anzahlen n an Städten (lasse n = 50 sein), ist in Deiner Lebenserwartungszeit keine optimale Lösung sicher gefunden - allenfalls aus der bisher untersuchten Menge die kleinste Strecke!
 
es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch Dein Computer wird für n = 500 in absehbarer Zeit keine Lösung bringen


6. Weiterführende Literatur history menue scroll up

 
der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen
 


7. Links zum Thema history menue scroll up

Viele gibt es - die meisten sind JAVA-basierte Spiele, um den erkannten Lösungsalgorithmus nach zu vollziehen. Wie gesagt, wenn Du vor hast, das Spiel noch am laufenden Tag zu beenden, verwende keine Scheibenzahl größer 20 - das ist dann schon nicht mehr zu schaffen.
http://www.blinde-kuh.de/spiele/hanoi/
http://www.cut-the-knot.org/recurrence/hanoi.shtml


8. Verwandte Themen history menue scroll up

Das Vorangestellte hilft wirtschaften für genau dieses Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.

das 8-Dame-Problem

des Cliquen-Problem

Domino-Problem

das Entscheidbarkeitsproblem

das Erfüllbarkeitsproblem

die Fibonacci-Zahlen

das Flaggenproblem

das Halteproblem

das Hamilton-Problem

das K-Farben-Problem

der Kaprekar-Algorithmus

die Magischen Quadrate

das PASCAL'sche Dreiecksproblem

das Philosophenproblem

das Königsberger-Brückenproblem

das Rucksackproblem

das Rundreiseproblem

das Springer-Problem

die Türme von Hanoi

das Wortproblem

das Wüstenfit-Problem

das 153-Problem

The Busy Beaver-Problem

Greedy Algorithm

SUDOKU

   

Worst-Case-Denken

Algorithmentheorie

Komplexität, Mächtigkeit und Aufwand

Praktische Elementaralgorithmen

Lösbarkeit und Problemlösungsstrategien

Klassische algorithmisch lösbare Probleme

Zufall und Computer

Graphentheorie

Petri-Netze

Informationsbegriff

Logo für die Signale

Nachrichten

Wissen

Systembegriff

Modellbegriff

Simulation

Denken und Sprache

Zahlen, Daten und Datentypen

Gegenläufigkeit und Verklemmung

Pattern-Matching

 
 



zur Hauptseite
© Samuel-von-Pufendorf-Gymnasium Flöha © Frank Rost im August 1995

... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehmen ;-)

„Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“

Diddi Hallervorden, dt. Komiker und Kabarettist

Diese Seite wurde ohne Zusatz irgendwelcher Konversationsstoffe erstellt ;-)