How many iterations are required for iterative-lengthening search when step costs are drawing from a continuos range [ϵ, 1]?

Question

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?

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.