UNIT 5

QUESTION BANK

1. Explain concept of branch & bound.
2. Explain algorithm of 0/1 knapsack using branch and bound and give one suitable example.
3. Explain the strategies of branch and bound.
4. Explain FIFO search with example.
5. Explain LIFO search with example.
6. Explain least cost search with example.
7. Write control abstraction of LC search and explain travelling salesman problem using branch and bound.
8. Draw state space tree generated by LC branch & bound for following knapsack instances:

N=4 M=15 and {p1,p2,p3,p4}={10,10,12,18}, {w1,w2,w3,w4}={2,4,6,9}.

9.      Difference between backtracking and branch & bound.

10. Explain the concept of bounding functions in branch & bound.