Home arrow Development Cycles arrow Branch and Bound Algorithm Technique
DEVELOPMENT CYCLES

Branch and Bound Algorithm Technique


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.

Author Info:
By: Barzan "Tony" Antal
Rating: 4 stars4 stars4 stars4 stars4 stars / 28
October 21, 2008
TABLE OF CONTENTS:
  1. · Branch and Bound Algorithm Technique
  2. · The Theory
  3. · The Theory, Continued
  4. · Conclusions of the Knapsack

print this article
SEARCH DEVARTICLES

Branch and Bound Algorithm Technique
(Page 1 of 4 )

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.


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2014 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials