1984 | OriginalPaper | Chapter
Das Branch-and-Bound-Verfahren (Binärer Entscheidungsbaum)
Author : Prof. Gustav Kastner
Published in: Operations Research mit BASIC auf Commodore 2000/3000, 4000/8000
Publisher: Gabler Verlag
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.