Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-06T14:21:43.470Z
Answers.LastActivityDate: 2018-08-11T12:20:10.373Z
Answers.LastEditDate: 2018-08-11T12:20:10.373Z
Answers.UserDisplayName: Dennis Soemers
Body: <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>
  
Tags: <search>
Title: How many iterations are required for iterative-lengthening search when step costs are drawing from a continuos range [ϵ, 1]?
UserDisplayName: alwaysLearningABC
ThreadText: # 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.
  
  
  ---
  
  