Branch and Bound II

Sei ein Lösungsraum L und eine Kostenfunktion c: L -> R gegeben, wobei eine Lösung l₀ zu finden ist

mit c(l₀) k für eine vorgegebene Schranke k oder

c(l₀) <= c(l) l L (globales Minimum)

dann ist es sinnvoll, bei einem Backtracking-Verfahren nach einer weiteren Kostenfunktion c': L' -> R zu suchen, die für Teil-Lösungen l' aus L' eine ``möglichst gute'' untere Schranke gibt für alle c(l) mit l L, wobei sich l von l' ableiten läßt.

Die Kostenfunktion c' kann dann eingesetzt werden, um zu entscheiden, ob sich das Weiterverfolgen einer Teil-Lösung l' lohnt, oder ob es besser ist, diesen Zweig abzuschneiden.

Beim Travelling-Salesman-Problem ist L die Menge aller Permutationen über die Orte 1..n und die Kostenfunktion die Länge einer Reiseroute. Die Kostenfunktion für Teil-Lösungen kann die bislang zurückgelegte Distanz berücksichtigen und eine untere Abschätzung über die noch zurückzulegende Strecke zu den noch nicht aufgesuchten Orten.