Branch-and-Bound (TSP): Weitere Iterationen

Da Reduktionskonstante und Summe aus zweitkleinstem Element gleich sind, müssen Fall (a) und (b) des 4. Schrittes durchgeführt werde. Es wird zunächst der Fall (a) für den Ast betrachtet.

(a) Ist die sich hier ergebene erneute Reduktionskonstante kleiner als die Summe der zweitkleinsten Elemente in Schritt 3, so wird dieser Ast weiterverfolgt. Es wird dann hierfür die reduzierte Matrix mit der gestrichenen Zeile und Spalte gewählt. Die Reduktionstionskonstante muss auf die obere Schranke addiert werden und ergibt die neue obere Schranke. Dieser Ast bedeutet, dass die Tour mit aufgenommen wird. 

Es wird nun also die zuletzt betrachtete reduzierte Matrix mit der gestrichenen Zeile und Spalte herangezogen:

Der Schritt 2 wird durchgeführt. Das bedeutet also wieder die Betrachung der Nullelemente innerhalb der Matrix und die Berechnung der Summe der zweitkleinsten Elemente der zugehörigen Zeile und Spalte:

In diesem Fall liegen nun eine Vielzahl an Werten vor. Am Besten geht man hier nun so vor, dass man eine Teilstrecke wählt, die an die bereits gefundene Teilstrecke anknüpft. Es wird gerade die Teistrecke betrachtet. Demnach würde sich hier empfehlen die Teilstrecken oder zu wählen. Es wird hier gewählt.  

Es ergibt sich demnach die Teilstrecke:

.

Es soll wieder der Zyklus  ausgeschlossen werden (da noch Knoten mitberücksichtigt werden soll). Dazu wird gesetzt. Danach wird die Matrix zeilen- und spaltenweise reduziert:

Es kann keine Reduktion vorgenommen werden. Deswegen bleibt die Reduktionskonstante bei . Das bedeutet also, dass die Aufnahme der Tour eine zusätzliche Reduktionskonstante von 0 aufweist und die Nichtaufnahme (Summe der zweitkleinsten Elemente) einen Wert von 4. Es ergeben sich demnach die Schranken und . Der Zweig wird nicht weiter verfolgt:

Es muss nun als nächstes für den Ast mit der Fall (b) betrachtet werden. Dieser Ast bedeutet die Nichtaufnahme der Teilstrecke . Hierfür wird nun die Matrix aus dem voherigen Abschnitt herangezogen (Schritt 2), vor Aufnahme der Teilstrecke :

Es wird dann das Element gesetzt (damit dieses nicht aufgenommen wird) und eine zeilen- und spaltenweise Reduktion der Matrix durchgeführt:

Die obige Matrix stellt nun die Ausgangsmatrix für den Ast mit dar. Hier wurde nun die Tour ausgeschlossen, indem gesetzt worden ist. Danach wurde die Reduktion vorgenommen. Es ergibt sich eine zusätzliche Reduktionskonstante von . Dies entspricht genau der Summe der zweitkleinsten Elemente. Die obere Schranke ist demnach . Es wird nun also dieser Ast verfolgt, indem wieder Schritt 3 durchgeführt wird:

Es wird die Strecke ausgewählt. Es handelt sich momentan um die Tour (1,3), da der Ast betrachtet wird, welcher die Tour ausschließt. Demnach muss das Element gesetzt werden um den Zyklus zu verhindern. Das Element ist bereits gleich unendlich gesetzt worden. Es wird als nächsten die Zeile und gestrichen und dann die Matrixreduktion vorgenommen:

Es konnte keine Reduktion der Matrix vorgenommen werden. Mit Berücksichtigung der Tour ergibt sich demnach die obere Schranke . Ohne Berücksichtigung der Tour muss zur Schranke die Summe der zweitkleinsten Elemente addiert werden, dies ergibt eine Schranke von . Der Entscheidungsbaum ergibt sich wie folgt:

Es ist nun deutlich zu erkennen, dass noch zwei Äste mit gleicher oberer Schranke existieren. Diese beiden Äste mit den Schranken müssen nun weiterverfolgt werden. Die anderen Äste müssen nicht weiter betrachtet werden, da die oberen Schranken größer sind. Das bedeutet und müssen nicht weiter betrachtet werden. Es muss immer von der Matrix ausgegangen werden, die zuletzt für den betrachteten Schritt durchgeführt worden ist. Bei dem Ast mit sind die Teistrecken und aufgenommen worden. Es wird hier die folgende Matrix herangezogen:

Für diese wird wieder Schritt 3 durchgeführt. Dies ergibt die zusätzliche Teilstrecke von mit der Summe . Da diese Teilstrecke nicht mit der bereits gegeben Tour verbunden werden kann, wird der Zyklus unterbunden, indem gesetzt wird. Danach wird wieder die Zeile und die Spalte gestrichen und die Matrixreduktion vorgenommen:

Es konnte keine Reduktion vorgenommen werden. Die obere Schranke ist demnach . Die obige Matrix stellt die Endmatrix für diesen Zweig dar. Es kann keine weitere Reduktion mehr vorgenommen werden und es gibt keine zweitkleineren Elemente mehr. Die beiden Nullelemente sind dabei die beiden letzten Teilstrecken, die in die Tour mit aufgenommen werden:

und .

Aus den in die Tour aufgenommenen Teilstrecken kann nun die Rundreise bestimmt werden:

Die Gesamtkosten entsprechen der oberen Schranke in der Matrix:

Aus dem Abschnitt mit der begrenzten Enumeration bzw. der vollständigen Enumeration ist bekannt, dass hier bereits die optimale Reihenfolge mit den minimalen Gesamtkosten von 172 GE vorliegt. Da die optimale Reihenfolge normalerweise aber unbekannt ist, muss auch noch der Ast mit untersucht werden, da diese Schranke gleich der hier ermittelten Schranke ist. Würde die hier emittelte Schranke über der von liegen müsste der Ast natürlich ebenfalls weiter verfolgt werden. Nur wenn die Schranke größer als die Schranke wäre, müsste dieser Ast nicht weiter verfolgt werden. 

Für den Ast mit der Schranke wird die folgende Matrix herangezogen:

Es wird nun wieder Schritt 3 angewandt. Es ergibt sich die Teilstrecke mit der Summe . Da diese Teilstrecke nicht mit der bereits gegeben Tour verbunden werden kann, wird der Zyklus unterbunden, indem gesetzt wird. Danach wird wieder die Zeile und die Spalte gestrichen und die Matrixreduktion vorgenommen:

Die Reduktion ergibt eine zusätzliche Reduktionskonstante von . Demnach wird bei Aufnahme der Tour zur Tour die obere Schranke zu . Dies liegt über der Schranke bei .

Bei Nichtaufnahme der Tour wird die obere Schranke bestimmt, indem die Summe aus den zweitkleinsten Elemente zur oberen Schranke hinzuaddiert wird: . Auch dieser Ast muss nicht weiter verfolgt werden, weil die Schranke über liegt. 

Der Entscheidungsbaum ergibt sich zu: