## Exercises #### Section 6.1 1. Use [Algorithm 6.1](LiB0048.html#579) (The Breadth-First-Search with Branch-and-Bound Pruning algorithm for the 0–1 Knapsack problem) to maximize the profit for the following problem instance. Show the actions step by step.  2. Implement [Algorithm 6.1](LiB0048.html#579) on your system and run it on the problem instance of [Exercise 1](LiB0013.html#131). 3. Modify [Algorithm 6.1](LiB0048.html#579) to produce an optimal set of items. Compare the performance of your algorithm with that of [Algorithm 6.1](LiB0048.html#579). 4. Use [Algorithm 6.2](LiB0048.html#589) (The Best-First Search with Branch-and-Bound Pruning algorithm for the 0–1 Knapsack problem) to maximize the profit for the problem instance of Exercise I. Show the actions step by step. 5. Implement [Algorithm 6.2](LiB0048.html#589) on your system and run it on the problem instance of [Exercise 1](LiB0013.html#131). 6. Compare the performance of [Algorithm 6.1](LiB0048.html#579) with that of [Algorithm 6.2](LiB0048.html#589) for large instances of the problem. #### Section 6.2 1. Use [Algorithm 6.3](LiB0049.html#603) (The Best-First Search with Branch-and-Bound Pruning Algorithm for the Traveling Salesperson problem) to find an optimal tour and the length of the optimal tour for the graph below. [](figu265_1_0.jpg) Show the actions step by step. 2. Write functions *length* and *bound* used in [Algorithm 6.3](LiB0049.html#603). 3. Implement [Algorithm 6.3](LiB0049.html#603) on your system, and run it on the problem instance of Exercise 7. Use different bounding functions and study the results. 4. Compare the performance of your dynamic programming algorithm (see [Section 3.6](LiB0030.html#331), Exercise 27) for the Traveling Salesperson problem with that of [Algorithm 6.3](LiB0049.html#603) using large instances of the problem. #### Section 6.3 1. Revise [Algorithm 6.4](LiB0050.html#618) (Cooper's Best-First Search with Branch-and-Bound Pruning algorithm for Abductive Inference) to produce the *m* most probable explanations, where *m* is any positive integer. 2. Show that if the diseases in [Example 6.4](LiB0050.html#610) were sorted in nonincreasing order according to their conditional probabilities, the number of nodes checked would be 23 instead of 15. Assume that *p*(*d*4) = 0.008 and *p*(*d*4, *d*1) = 0.007. 3. A set of explanations satisfies a comfort measure *p* if the sum of the probabilities of the explanations is greater than or equal to *p*. Revise [Algorithm 6.4](LiB0050.html#618) to produce a set of explanations that satisfies *p*, where 0 ≤ *p* ≤ 1. Do this with as few explanations as possible. 4. Implement [Algorithm 6.4](LiB0050.html#618) on your system. The user should be able to enter an integer *m*, as described in Exercise 11, or a comfort measure *p*, as described in Exercise 13. #### Additional Exercise 1. Can the branch-and-bound design strategy be used to solve the problem discussed in Exercise 34 in [Chapter 3](LiB0024.html#252)? Justify your answer. 2. Write a branch-and-bound algorithm for the problem of scheduling with deadlines discussed in [Section 4.3.2](LiB0035.html#412) 3. Can the branch-and-bound design strategy be used to solve the problem discussed in Exercise 26 in [Chapter 4](LiB0032.html#359)? Justify your answer. 4. Can the branch-and-bound design strategy be used to solve the Chained Matrix Multiplication problem discussed in [Section 3.4](LiB0028.html#290)? Justify your answer. 5. List three more applications of the branch-and-bound design strategy.