Beim Rundreiseproblem (auch Traveling Salesman Problem (TSP) genannt) muss ein Rundreisender nacheinander N Orte besuchen ohne einen einzigen zweimal anzufahren. Die letzte Reiselinie soll ihn genau an seinen Start(Heimat)ort zurückführen. Gesucht ist der insgesamt kürzeste Reiseweg für die Runde.

In Bild 1 sind die zu besuchenden Orte schematisch durch blauer Kreise gekennzeichnet und die Reisestrecke durch einen roten Geradenzug. Es wird angenommen, dass es unabhängig von der Lage (den Koordinaten) der (hier 12) blauen Kreise keine Wegekreuzungen beim kürzesten Reiseweg geben kann. Ob das auch bereits mathematisch bewiesen oder nur eine Vermutung ist, entzieht sich meiner Kenntnis [ich wäre für einen entsprechenden Hinweis von einem mathematischen Fachmann sehr dankbar].

Wir wollen diese Annahme durch ein Simulationsprogramm zu widerlegen versuchen, d. h. Ortslagekonstellationen suchen, bei denen der kürzeste Reiseweg mindstens zwei Teilstrecken einhält, die sich kreuzen.

Da es bei N unterschiedlichen Orten insgesamt 0.5 * (N - 1)! verschiedene Rundreisewege der besagten Art gibt, ist man mit N >> 10 sehr schnell am Ende seiner Rechenkunst (selbst mit Hochleistungsrechnern). Es soll für die Simulation daher N maximal 12 sein, aber mindestens 4. Bei N = 4 kann man einfach zeigen, dass eine Rundreise mit Wegekreuzung immer länger ist als der einzige Weg ohne Kreuzung. Aber, gilt das auch für N > 4?

Die Kreuzungsfreiheit kann unter Nutzung der Lösung von Aufgabe Nr. 390 (bei c#) (Schnittpunkt zweier Geraden endlicher Länge) nachgewiesen werden. Insgesamt sollen etwa 1.000 zufällige Ortslagekonstellationen der N Orte erzeugt und hinsichtlich ev. vorhandener Kreuzungen untersucht werden.

Viel Spaß!