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

Copyright Disclaimer:
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.