Sukzessive Einbeziehung
Die Sukzessive Einbeziehung ist ein Algorithmus zum Lösen von kombinatorischen Optimierungsproblemen wie zum Beispiel dem Problem des Handlungsreisenden. Für diese Probleme liefert dieses heuristische Eröffnungsverfahren eine approximierte Lösung. Es wurde 1964 von Robert L. Karg und Gerald L. Thompson entwickelt[1].
Die Sukzessive Einbeziehung gehört zu den Greedy-Algorithmen und lässt deswegen keine Aussage über die Qualität des Ergebnisses zu. In der Praxis sind die Ergebnisse jedoch meist besser als die anderer Methoden, wie zum Beispiel die Nearest-Neighbor-Heuristik.
Der Algorithmus beginnt mit einem beliebigen Kreis aus 2 Punkten und fügt sukzessiv weitere Punkte sinnvoll in den Kreis ein, so dass zum Ende ein Hamiltonkreis entsteht, der alle Punkte beinhaltet.
Beispiel des Algorithmus
Gegeben sind 6 Punkte, die sich in einem 2-dimensionalen Koordinatensystem befinden. Als Ausgangspunkt dienen zwei beliebige Punkte A und B, die den Kreis A – B – A bilden.
Im ersten Schritt wird der minimale Abstand von einem weiteren Punkt zu den im Kreis enthaltenen Punkten berechnet. In diesem Fall sind das die Punkte A und B. Dieses vorgehen wird für alle Punkte wiederholt, die noch nicht eingebunden sind. Anschließend wird von den minimalen Abständen das Maximum gebildet und der entsprechende Punkt in den Kreis eingefügt. Im vorhandenen Beispiel ist das der Punkt C.
Der neue Kreis bildet nun die Route A – B – C – A.
An dieser Stelle spielt es für die Weglänge keine Rolle, zwischen welchen Punkten Punkt C in die Strecke eingefügt wird. Wenn jedoch 3 oder mehr Punkte vorhanden sind, wird der Punkt C so in den Kreis integriert, dass die resultierende Länge für diesen minimal ist.
Im nächsten Schritt werden wieder die minimalen Abstände von den verbleibenden Punkten berechnet. Diesmal wird neben Punkt A und B auch der Punkt C berücksichtigt, da dieser nun in dem Kreis einbezogen ist.
Es wird der Punkt E in den Kreis einbezogen. Hierbei ist es entscheidend, an welcher Stelle dieser Punkt eingefügt wird. Daher wird geprüft, welche Möglichkeit die geringste Strecke zur Folge hat. In diesem Fall kann der Punkt E wie folgt in den gesamten Kreis integriert werden:
- A – B – C – E – A
- A – B – E – C – A
- A – E – B – C – A
Die letztgenannte Möglichkeit hat die minimale Streckenlänge zur Folge und wird daher gewählt. Dieses Vorgehen wird so oft wiederholt, bis alle Punkte in dem Kreis integriert wurden. In Bild 3 ist der Streckenverlauf zu sehen, den der Algorithmus für dieses Beispiel berechnet hat.
Einzelnachweise
- R. L. Karg, G. L. Thompson: A Heuristic Approach to Solving Travelling Salesman Problems. In: Management Science. 10, Nr. 2, 1964, ISSN 0025-1909, S. 225–248. doi:10.1287/mnsc.10.2.225.