ALGORITHMS - BRANCH AND BOUND
The branch and bound algorithm is a pruning technique that allows us to examine a given path, decide whether to keep considering it or to disregard it based on the evaluation of the path in comparison with others so far. As mentioned above, the branch and bound search algorithm considers the best path so far, while other algorithms look at the best successor step in a given path. The path cost for each route explored is stored and used to sort the choices.
The branch and bound is a depth first search based
algorithm that considers the best path so far, backtracking whenever it
encounters a node whose value is larger than its current upper bound. The
algorithm terminates when all paths have been explored or pruned. The algorithm
is both optimal and complete, as in it will search all the possible solutions
and find the best one. The advantages of the search are low memory use and
the availability of the best partial path so far.
Fig. 1 (demo from http://www.utia.cas.cz/user_data/PR_dept/fs/fs_algorithms.html#References)
Our task is to select 2 items out of the total number of 6 items (as shown
in the figure above) so as to
maximize an adopted criterion function. During
demonstrations the red color denotes criterion value
computation, yellow
color denotes a much faster criterion value prediction.
In short, branch and bound is an algorithm technique to find the optimal solution by keeping the best solution found so far. If a partial solution examined at a given point cannot do better than the best, work on it is abandoned.