1984 | OriginalPaper | Buchkapitel
Das Branch-and-Bound-Verfahren (Binärer Entscheidungsbaum)
verfasst von : Prof. Gustav Kastner
Erschienen in: Operations Research mit BASIC auf Commodore 2000/3000, 4000/8000
Verlag: Gabler Verlag
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Das Branch-and-Bound-Verfahren gehört mit der Begrenzten Enumeration und der Dynamischen Planungsrechnung zu den Entscheidungsbaumverfahren und steht mit ihnen der Vollständigen Enumeration gegenüber. Während man bei der Begrenzten Enumeration streng sequentiell, bei der Dynamischen Planungsrechnung streng parallel vorgeht, um Teillösungen auszuschließen, die für eine Optimallösung nicht in Frage kommen, stellt das Branch-and-Bound-Verfahren eine Mischung aus beiden dar. Man verfolgt im Entscheidungsbaum einen Zweig solange, wie er vermuten läßt, daß er zur Optimallösung führt. Dabei findet man neue Optimalitätsgrenzen (bound), durch die Teile des Entscheidungsbaumes abgezweigt (branch) werden. Beim Branch-and-Bound kann man also auf allen Stufen des Entscheidungsbaumes gleichzeitig Knoten in der Berechnung haben, die noch zur Optimallösung führen können.