Rundreiseproblem oder Problem des Handlungsreisenden - The Traveling Sales-Mans Problem

Letztmalig dran rumgefummelt: 08.04.22 11:34:45

	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: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	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

	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

	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 ;-) Berechnungstabelle für das Acht-Knoten Rundreiseproblem hier im EXEL-Format zum Download
	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

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

	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 :-(
	... das Rundreiseproblem in einer Lösungsvariante von Loris Kunze & Vincent Ludewig im Schuljahr 2018/19 Projekt-Materialien Projekt-Materialien

5. Zusammenfassung

	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

	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

	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

	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