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.
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:
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;
add in open;
if (h equals 0) // solution is found
recursively print the route between this leaf node and the root
solution = TRUE;
if (solution equals FALSE)
Now on the final page you will find the B&B approach implemented on the Knapsack problem.