Branch Bonud Chp 6

Contents of Chapter 8 • Chapter 8 Branch-and-Bound – – – – –

8.1 8.2 8.3 8.4 8.5

The method 0/1 Knapsack problem Traveling salesperson Efficiency considerations References and readings

8.1 The Method • Branch-and-bound – Referring all state space search methods in which all children of the E-node are generated before any other live node can become the E-node – Section 7.1 • DFS (Figure 7.2)  backtracking • BFS (Figure 7.3)  B&B • D-search (Figure 7.4)  B&B – BFS-like state space search • Called FIFO search • Using queue – D-search-like state space search • Called LIFO search • Using stack – Like the backtracking • B&B uses the same terminology in Section 7.1 • B&B uses the bounding function

8.1 The Method • Example 8.1 [4-queens] – Figure 8.1

– For this problem, the backtracking is superior to B&B • Why? (compare Figure 7.6 (backtracking) and Figure 8.1 (B&B)) • Any technique to improve B&B ?  LC (least cost) search