Laut Sedgewick (Algorithmen in C) kann man Überschneidungen in Touren entfernen, wenn man folgendes Verfahren anwendet:
Falls eine Strecke AB eine andere Strecke CD überschneidet, löscht man die beiden Strecken aus der Tour und ersetzt sie durch die neuen Strecken AD und CB.
In vielen Fällen funktioniert dieses Verfahren ganz gut, aber in einem von Sedgewick selbst vorgestellten Beispiel gibt es Probleme, wie ich durch eigene Versuche herausgefunden habe:
Durch Anwendung des Sedgewick-Verfahrens auf die Tour oben links entsteht die Tour oben rechts. Die vorhandene Überschneidung wurde durch eine neue Überschneidung ersetzt. Wendet man das Verfahren nun noch einmal an, indem man die Städte umbenennt (aus D wid B und aus B wird D), dann erhält man wieder die Ausgangskonfiguration.
Durch eine alternative Methode der Überschneidungs-Entfernung käme man zu einem viel besseren Ergebnis:
Falls eine Strecke AB eine andere Strecke CD überschneidet, löscht man die beiden Strecken aus der Tour und ersetzt sie durch die neuen Strecken AC und DB.
Natürlich hätte auch diese Alternative zu einem Endlos-Zyklus wie oben führen können. Ein "vernünftiger" Algorithmus sollte beide Alternativen kennen und wahlweise anwenden können.
Für Schüler, die einen solchen Algorithmus in Java implementieren wollen, stellt sich zunächst ein anderes Problem: Wie erkennt man überhaupt solche Überschneidungen?
Erkennen von Überschneidungen
Das ist ein Thema, das zu behandeln ich noch keine Zeit hatte. Aber es steht auf der ToDo-List ganz weit oben...