1 of 10

Branch and Bound

Branch and Bound is another method to systematically search a solution space. Just like backtracking, we will use bounding functions to avoid generating subtrees that do not contain an answer node. However branch and Bound differs from backtracking in two important manners:

1. It has a branching function, which can be a depth first search, breadth first search or based on bounding function.

2. It has a bounding function, which goes far beyond the feasibility test as a mean to prune efficiently the search tree.

Amity School of Engineering & Technology

2 of 10

  • Live node is a node that has been generated but whose children have not yet been generated.
  • E-node is a live node whose children are currently being explored.�Dead node is a generated node that should not be expanded or explored further.
  • Answer node- Those solution states S for which path from root to S defines a tuple which is a member of the set of solutions.

Amity School of Engineering & Technology

3 of 10

Three types of searching strategies used in Branch & Bound:-

  1. FIFO (First In First Out) Branch &Bound Search
  2. LIFO (Last In First Out) Branch &Bound Search
  3. LC(Least Cost) Branch &Bound Search

​

Amity School of Engineering & Technology

4 of 10

FIFO (First In First Out) Branch &Bound Search�

  • FIFO Branch and Bound is a BFS.
  • In FIFO Branch and Bound , children of E-Node (or Live nodes) are inserted in a queue.
  • Implementation of list of live nodes as a queue�     

Delete() Removes the head of the Queue�      Add() Adds the node to the end of the Queue

​

Amity School of Engineering & Technology

5 of 10

Amity School of Engineering & Technology

6 of 10

LIFO (Last In First Out) Branch &Bound Search�

  • LIFO Branch and Bound is a D-search (or DFS).�In LIFO Branch and Bound children of E-node (live nodes) are inserted in a stack�Implementation of List of live nodes as a stack�     Delete() Removes the top of the stack�    ADD() Adds the node to the top of the stack

Amity School of Engineering & Technology

7 of 10

Amity School of Engineering & Technology

8 of 10

LC(Least Cost) Branch &Bound Search�

  • The selection rule for the next node-E in the branch FIFO or LIFO and linked is sometimes “blind”. that is, the selection rule gives no preference to a node that has a very good chance of quickly finding a response node.
  • The search for a response node can often be speeded by using a “intelligent” ranking function. It is also called the approximate cost function “Ĉ”.

​

Amity School of Engineering & Technology

9 of 10

  • Branching: A set of solutions, which is represented by a node, can be partitioned into mutually (jointly or commonly) exclusive (special) sets. Each subset in the partition is represented by a child�of the original node.

Amity School of Engineering & Technology

10 of 10

  • Lower bounding: An algorithm is available to calculate a lower bound on the cost of any solution in a given subset.

Each node X in  search tree is associated with a cost of : Ĉ(X)�C = the cost of the reaching current node, X(E-node) form  root + The cost of reaching an answer node form X.�Ĉ=g(X)+H(X).

​

Amity School of Engineering & Technology