Exercise 3.11 Consider the algorithm sketched in the counterexample of the box on page 105:

(a) When can the algorithm stop? (Hint: it does not have to wait until the forward search finds a path to a goal).

(b) What data structures should be kept?

(c) Specify the algorithm in full.

(d) Show that it finds the optimal path.

(e) Give an example where it expands (many) fewer nodes than A∗.