<p>In the title of the question, you write (emphasis mine):</p>

<blockquote>
  <p><strong>step</strong> costs are drawn from a continuous range $[\epsilon, 1]$</p>
</blockquote>

<p>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.</p>

<hr>

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

CC BY-SA 4.0
2018-08-06T14:21:43.470Z
2018-08-11T12:20:10.373Z
2018-08-11T12:20:10.373Z
Dennis Soemers
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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?</p>

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

(Asked by: username_0 on 2018-04-23)

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?

**Tags:** search


---

## 1 answers

### Answer by username_1 on 2018-08-06. Score: 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.


---

