This is AI: A Modern Approach, 3.17c. The solution manual gives the answer as $\frac{d}{\epsilon}$, where $d$ is the depth of the shallowest goal node.

Iterative lengthening search uses a path cost limit on each iteration, and updates that limit on the next iteration to the lowest cost of any rejected node.

I have seen this question posted elsewhere as, "What is the number of iterations with a continuous range $[0, 1]$ and a minimum step cost $\epsilon$?" In that case, I agree that the minimum number of iterations is $\frac{d}{\epsilon}$ because you would need to increase the path cost limit by a minimum of $\epsilon$ with each iteration.

However, with a continuous range of $[\epsilon, 1]$, it seems there is an infinite range and that the number of iterations is potentially infinite, since there is no minimum step cost. Should this solution actually be infinite?


1 Answer 1


In the title of the question, you write (emphasis mine):

step costs are drawn from a continuous range $[\epsilon, 1]$

If step costs are drawn from that range, it means that every step has a cost of at least $\epsilon$, and at most $1$. This leads back to the case that described in the question that you already understand.

Note that the book (at least, the third edition of the book) does state in the question that $0 < \epsilon < 1$. Of course, the question would not make much sense in the first place if negative costs were allowed.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .