Branch and Bound Algorithm in Artificial Intelligence

Branch and Bound Algorithm:

This strategy applies to problems having a graph search space where more than one alternative path may exist between two nodes. This strategy saves all path lengths from a node to all generated nodes and chooses the shortest path for further expansion. Then it compares the new path lengths with all old ones and again chooses the shortest path for expansion. In this way, any path to a good node is certain to be a minimum-length path. The Branch and Bound algorithms are given as follows:

Step 1: Form a queue of partial paths. Let the initial queue be a zero-length, zero-step path from the root node to nowhere.

Step 2: Until (queue is empty) or (goal is found) find if the first path in the queue reaches the goal node.

(a) If the first path reaches the goal node, do nothing.
(b) If the first path does not reach the goal node then,
(i) Remove the first path from the queue.
(ii) Form a new path from the removed path by extending one step.
(iii) Sort the queue in increasing order of the cost accumulated so far.

Step 3: If the goal has been found then return SUCCESS else return FAILURE.

Step 4: End Branch and Bound algorithm.