Branch and Bound Algorithm Technique
(Page 1 of 4 )
Branch and bound is another algorithm technique that we are going to present in our multi-part article series covering algorithm design patterns and techniques. B&B, as it is often abbreviated, is one of the most complex techniques and surely cannot be discussed in its entirety in a single article. Thus, we are going to focus on the so-called A* algorithm that is the most distinctive B&B graph search algorithm.
If you have followed this article series then you know that we have already covered the most important techniques such as backtracking, the greedy strategy, divide and conquer, dynamic programming, and even genetic programming. As a result, in this part we will compare branch and bound with the previously mentioned techniques as well. It is really useful to understand the differences.
Branch and bound is an algorithm technique that is often implemented for finding the optimal solutions in case of optimization problems; it is mainly used for combinatorial and discrete global optimizations of problems. In a nutshell, we opt for this technique when the domain of possible candidates is way too large and all of the other algorithms fail. This technique is based on the en masse elimination of the candidates.
You should already be familiar with the tree structure of algorithms. Out of the techniques that we have learned, both the backtracking and divide and conquer traverse the tree in its depth, though they take opposite routes. The greedy strategy picks a single route and forgets about the rest. Dynamic programming approaches this in a sort of breadth-first search variation (BFS).
Now if the decision tree of the problem that we are planning to solve has practically unlimited depth, then, by definition, the backtracking and divide and conquer algorithms are out. We shouldn't rely on greedy because that is problem-dependent and never promises to deliver a global optimum, unless proven otherwise mathematically.
As our last resort we may even think about dynamic programming. The truth is that maybe the problem can indeed be solved with dynamic programming, but the implementation wouldn't be an efficient approach; additionally, it would be very hard to implement. You see, if we have a complex problem where we would need lots of parameters to describe the solutions of sub-problems, DP becomes inefficient.
If you still need a real-world proof, then there's the fifteen puzzle. One of the most straightforward implementations of dynamic programming would require 16 distinctive parameters to represent the optimum values of the solutions of each sub-problem. That means a 16-dimensional array. You see, this is why DP is out of question!
Let's move on and learn more about Branch and Bound. Turn the page.
Next: The Theory >>
More Development Cycles Articles
More By Barzan "Tony" Antal
