Consider again the search tree of Fig. 5.4. (a) Suppose the tree is traversed using branch and bound in a depth-first fashion. At each nonleaf node, the left or right branch is taken first with equal...

Consider again the search tree of Fig. 5.4. (a) Suppose the tree is traversed using branch and bound in a depth-first fashion. At each nonleaf node,

the left or right branch is taken first with equal probability. Compute the

expected lower bound obtained, and the expected best incumbent solution

value obtained, after k (nonroot) nodes are processed, for k = 1,..., 6. (b)

Now do the same for a breadth-first search. For k ≥ 4, one of the level-one

nodes is completed before any nodes under the other level-one node are processed. Note that in the early part of the search, depth-first obtains good

incumbent solutions more quickly, and breadth-first obtains good bounds

more quickly.