Home > Informatik > Optimierungsprobleme

Entfernen von Überschneidungen

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:

Entfernung von Überschneidungen

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.

Eine alternative Entfernung der Überschneidung

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...

Das Traveling Salesman Problem ist eines der bekanntesten Optimierungsprobleme der Informatik. Algorithmen, die das TSP auf vernünftige Weise lösen, lassen sich auch für die Lösung vieler anderer ähnlicher Probleme einsetzen, zum Beispiel bei der Herstellung von Leiterplatten.