Branch-and-Bound

Vorgehensweise

Bound (Begrenzung)

Der Bound-Schritt hat die Aufgabe, bestimmte Zweige des Baumes "abzuschneiden", d.h. in der weiteren Berechnung nicht mehr zu betrachten, um so den Rechenaufwand zu begrenzen. Dies erreicht der Algorithmus durch Berechnung und Vergleich zweier Schranken. Der Weg von der Wurzel des Baumes zu einem Teilproblem bildet die untere Schranke ("lower bound") dieses Teilproblems – auf welche Weise sich auch der weitere Weg durch den Baum gestaltet, der Weg zum Teilproblem ist festgelegt. Als obere Schranke dient eine vorerst optimale zulässige Lösung. Diese erhält man durch Berechnung eines kompletten Zweiges (von der Wurzel zu einem Blatt des Entscheidungsbaumes) – ebenso ist es aber auch möglich, eine Heuristik vor dem eigentlichen Branch-and-Bound Verfahren zu berechnen und die erhaltene Lösung als obere Schranke zu verwenden.

Übersteigt nun die untere Schranke in einem Teilproblem die obere Schranke, so kann der aktuell betrachtete Teilbaum "abgeschnitten" werden, da es mindestens eine bessere zulässige Lösung gibt, die nicht mehr erreicht werden kann. Sollte hingegen eine Komplettlösung berechnet werden, die besser als die obere Schranke ist, so wird diese ersetzt und als neue optimale Lösung vorgehalten.-->

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Branch-and-Bound aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung