Branch and Bound Algorithm Technique - The Theory
(Page 2 of 4 )
On the previous page you saw that the most promising approach was dynamic programming. Basically, let's continue to look at breadth-first search [BFS]. The drawback is that the complexity of BFS is exponential. We need an algorithm that ameliorates this issue by reducing a whole number of possible candidates that just aren't satisfactory and, thus, won't contribute to the optimal solution. Answer: the B&B.
That is what branch and bound does. This algorithm injects some intelligence into the naïve but complex breadth-first search. Instead of searching throughout the entire decision/search tree structure, it instills some sort of criteria, according to which the complexity of the BFS can be reduced. We can do this by adding "costs."
For example, if we calculate the distance of each node in terms of "how far" it is located from the initial root node configuration and "how close" it is from the solution, then the distance/cost is the sum of the aforementioned two distances. However, as you can surely see, the second distance relies on heuristics. Thus, it's just a guess.
Moreover, we can move through this tree based on the instilled costs; a node is a more possible candidate toward the solution if its cost is less than other nodes. What we did is add an essence of depth-search to the breadth-first meaning; meaning, there is going to be a priority queue, according to which we are running the breath-first search. The traditional BFS runs from left to right, but now we'll have the priority queue instead.
The beauty of this approach is that we haven't lost the not-so-possible candidates. You see, they are stored somewhere on the end of the priority queue, so this algorithm doesn't neglect the rest of the possible options. Summing these up, this is in fact a typical Branch and Bound algorithm technique. And yes, it relies on the guessing game.
B&B is composed of two main actions, but there's an additional step. The first step is, as its name suggests, the branching. This is where we define the tree structure from the set of candidates in a recursive manner. The second action is called bounding since this procedure calculates the upper and lower bounds of each node from the tree.
Furthermore, there's the additional pruning step that we can add. In a nutshell, it means that if the lower bound for some node of the tree is greater than the upper bound of some other node of the tree, then the first node of the tree can be "discarded" (remember, it does not mean eliminate) from the search. A variable always holds the value of the global minimum upper bound.
All in all, B&B is very similar to backtracking. The main differences are that the former is used only in case of optimization problems, whereas backtracking cannot be, and B&B doesn't limit us to a particular way of traversing the tree (depth-first search / preorder as with backtracking). Backtracking always picks one single successor from the candidates, while B&B always has the entire list of successors in the queue.
Next: The Theory, Continued >>
More Development Cycles Articles
More By Barzan "Tony" Antal
