Home arrow Development Cycles arrow Page 3 - 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 - The Theory, Continued
(Page 3 of 4 )

Here we are going to sum up the key elements of the B&B algorithm technique. Later on a typical problem will be presented, namely the knapsack problem. You will surely understand by the end of this article why the knapsack is an NP-hard problem that is definitely an optimization problem. But first let's see the resume of B&B.

A branch and bound algorithm is based on an advanced breadth-first search. The said BFS is done with a priority queue [PQ] instead of the traditional list. You can imagine the priority queue as any other queue, except that it is sorted. This means that the highest priority element is always on the first position.

It is crucial to understand the importance of these two functions: g(x) and h(x). The first function, g(x), calculates the distance between the x node and the root node. The latter, h(x), is a heuristic function because it estimates how close the said x node is to the solution (leaf). The heuristic function ought to return 0 in the case of a solution leaf (since the distance is zero). The efficiency of the B&B relies on this function.

Moreover, we can say that f(x) = g(x) + h(x) is a distance-plus-cost heuristic function itself, too. The g(x) part is the path-cost function, while the h(x) part is the admissible heuristic estimate; the sum of these two is the f(x). At the beginning of this article we mentioned the A* (A star) algorithm. This is when it comes into the picture.

The A* is a best-first, graph search algorithm. It is used when we want to find the least-cost path from an initial node to a specified goal node. This A* algorithm works on the basis of the aforementioned f(x) distance-plus-cost heuristic function. It starts with the initial node and expands it with the lowest f(x) value (lowest cost-per-benefit). But it stores all of the partial solutions in the priority queue (unexpanded leaf nodes).

This particular variation of the B&B algorithm works in the same fashion. We are going to work with two lists: open and close. In the former we store all of the non-expanded configurations, while the latter stores the expanded configurations. A solution is found only if the h(x) returns 0 (thus, a solution leaf) or the PQ queue becomes empty.

Here's a brief guide in pseudocode:

Procedure B&B:

open := initial configurations;

g := 0; f := h; solution := FALSE;

while ((h NOT equal 0) AND (open NOT empty)) do

t := node with the lowest f value;

expand this t node with its successors;

for each successor of t node do

g := g(t) + cost of the expansion; // this cost is often = 1

if (current successor is part of close OR empty)

then if (g < g(current configuration))

then link the current successor in the path;

set the new g value;

if (this successor found in close)

add in open;

end if;

end if;

else

add in open;

end for;

if (h equals 0) // solution is found

recursively print the route between this leaf node and the root

solution = TRUE;

end if;

end while;

if (solution equals FALSE)

no solutions;

end procedure;

Now on the final page you will find the B&B approach implemented on the Knapsack problem.


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-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials