Session 08

Question 1

Different search techniques in B&B ?

Answer 1

1. LC Search
2. BFS
3. DFS

Question 2

Characteristics of B&B ?

Answer 2

• Optimal Solution
• Upper and Lower bound
• Pruning
• Backtracking

Question 3

Applications of B&B ?

Answer 3

• Travelling salesman
• Knapsack
• Resource allocation
• Network optimization
• Game playing

Question 4

Adv and Disadv of B&B ?

Answer 4

Adv :
1. Optimal solution
2. Reduces search spaces
3. Proven performance
4. Incremental improvement

DisAdv :
1. Exponential time complexity
2. Need lot of memory
3. Sensitive to problem specific parameters
4. Limited scalability

Question 5

Classifications of B&B ?

Answer 5

1. FIFO B&B (BFS)
2. LIFO B&B (DFS)
3. LC (Least Cost) B&B