On page iterative-lengthening-page, we mentioned iterative lengthening search, an iterative analog of uniform cost search. The idea is to 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.
1. Show that this algorithm is optimal for general path costs.
2. Consider a uniform tree with branching factor $b$, solution depth $d$, and unit step costs. How many iterations will iterative lengthening require?
3. Now consider step costs drawn from the continuous range $[\epsilon,1]$, where $0 < \epsilon < 1$. How many iterations are required in the worst case?
4. 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.