  |
 |
|
|
|
|
|
InformatikBacktracking |
|
Das Rundreise-Problem Beim Rundreise-Problem oder Problem des Handlungsreisenden (travelling salesman problem) ist eine Reihenfolge von n Städten gesucht, so dass jede Stadt (außer dem Ausgangsort) genau einmal besucht wird, die Reise wieder am Standort endet und die Länge der Rundreise minimal ist. 
Dabei legen wir die Entfernungen der Städte in einer Entfernungstabelle fest, wie sie aus Atlanten oder Autokarten bekannt sein dürfte. Ausgangspunkt unserer Reise ist Aachen, da wir die Städte alphabetisch durchnummeriert haben (Aachen = 1). Wir versuchen, dieses Problem zu lösen, indem wir bei jedem Schritt die Menge der noch möglichen Lösungen durchgehen, die jeweils durch eine Verzweigung (branch) in einem Entscheidungsbaum dargestellt werden könnte. 
Das Abarbeiten der Alternativen kann verkürzt werden, indem man eine obere Schranke (bound) vorgibt und alle Touren verwirft, deren bisherige Länge diese Schranke überschreitet. Für diese Schranke wählt man zunächst eine sehr hohe Zahl, dann jeweils das Minimum der bisher gefundenen Rundreisen. Wird noch eine kürzere Route gefunden, so wird dieser Wert der Schranke zugewiesen. Nach diesen grundlegenden Lösungsprinzipien: verzweige (branch) und beschränke (bound) wird das Verfahren Branch & Bound genannt, es wurde von 1963 zum ersten Male als Lösung für das Travelling-Salesman-Problem publiziert.
|
