We mentioned iterative lengthening search, an iterative analog of uniform cost search. The idea is in use increasing limits on path cost. If a node is generated whose path cost exceeds the current limit, it is immediately discarded, for each new iteration the limit is set to the lowest path cost of any node discarded in the previous iteration.

a. Show that this algorithm is optimal for general path costs.

b. Consider a uniform tree with branching factor b, solution depth d. and unit step costs. How much iteration will iterative lengthening require?

c. Now consider step costs drawn from the continuous range [0. 1] with a minimum positive cost. How much iteration is required in the worst case?

d. Implement the algorithm and apply it to instances of the 8-puzzle and traveling salesperson problems. Compare the algorithm’s performance to that of uniform-cost search, and comment on your results.