Essential Algorithms by Stephens Rod
Author:Stephens, Rod
Language: eng
Format: epub, pdf
Publisher: Wiley
Published: 2013-07-17T04:00:00+00:00
Branch and Bound
Branch and bound is a technique for searching trees more effectively than an exhaustive search does. After it moves down a branch in the tree, the algorithm calculates the best possible outcome it can achieve down that branch. If the best possible outcome won't be an improvement over the best solution that has already been found, the algorithm abandons that branch and doesn't continue down its subtree. Depending on the specific data values, this can save a huge amount of time.
For example, suppose a partition problem algorithm keeps track of the current total weight in each of the two groups it is building and the total weight of the items that have not yet been assigned to a group. Now suppose the algorithm has reached a point where group 0 has a total weight of 100, group 1 has a total weight of 50, and the unassigned items have a total weight of 20. Suppose also that the algorithm has already found a solution in which the two groups have weights that differ by 20.
If the algorithm were to assign all the remaining items to group 1, group 0 would have a total weight of 100, and group 1 would have a total weight of 70, a difference of 30. But the algorithm has already found a solution in which the difference is only 20. The current test solution cannot be improved enough to make it better than the current best solution. In that case, the algorithm can stop working on its current solution without assigning the rest of the items.
The following pseudocode shows a high-level branch and bound algorithm for the optimization version of the partition problem:
StartBranchAndBound() <Initialize best solution so it is replaced by the first test solution> BranchAndBound(0) End StartBranchAndBound BranchAndBound(Integer: next_index) // See if we are done. If <next_index > max_index> // We have assigned all items, so we are at a leaf node. <If the test solution is better than the best solution, save it> Else // We have not assigned all items, so we are not at a leaf node. If <the test solution cannot be improved enough to beat the current best solution> Then Return <Assign item next_index to group 0> BranchAndBound(next_index + 1) <Unassign item next_index to group 0> <Assign item next_index to group 1> BranchAndBound(next_index + 1) <Unassign item next_index to group 1> End If End BranchAndBound
This algorithm is similar to the exhaustive search algorithm, except that it determines whether the test solution can be improved enough to beat the current best solution, and it returns without recursion if it can't.
Branch and bound often trims many branches and their subtrees from the decision tree, so it can be much faster than an exhaustive search.
For example, in one test, while trying to divide 20 items into two groups of equal weight, a full exhaustive search visited 2,097,150 nodes, but a branch and bound search visited only 774,650 nodes. When both algorithms were allowed to use the “short circuit” described in
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Deep Learning with Python by François Chollet(12568)
Hello! Python by Anthony Briggs(9912)
OCA Java SE 8 Programmer I Certification Guide by Mala Gupta(9795)
The Mikado Method by Ola Ellnestam Daniel Brolund(9777)
Dependency Injection in .NET by Mark Seemann(9336)
Algorithms of the Intelligent Web by Haralambos Marmanis;Dmitry Babenko(8293)
Test-Driven iOS Development with Swift 4 by Dominik Hauser(7758)
Grails in Action by Glen Smith Peter Ledbrook(7693)
The Well-Grounded Java Developer by Benjamin J. Evans Martijn Verburg(7557)
Becoming a Dynamics 365 Finance and Supply Chain Solution Architect by Brent Dawson(7040)
Microservices with Go by Alexander Shuiskov(6805)
Practical Design Patterns for Java Developers by Miroslav Wengner(6717)
Test Automation Engineering Handbook by Manikandan Sambamurthy(6656)
Secrets of the JavaScript Ninja by John Resig Bear Bibeault(6409)
Angular Projects - Third Edition by Aristeidis Bampakos(6065)
The Art of Crafting User Stories by The Art of Crafting User Stories(5596)
NetSuite for Consultants - Second Edition by Peter Ries(5531)
Demystifying Cryptography with OpenSSL 3.0 by Alexei Khlebnikov(5335)
Kotlin in Action by Dmitry Jemerov(5062)
