Answers.Body: <p>In practice, you can consider that IDS is a cheap way to implement a breadth-first search (BFS).</p>
  <p>When the branching factor is high, both algorithms have similar computational costs <span class="math-container">$O(B^P)$</span>, where <span class="math-container">$P$</span> is the length of the solution path and <span class="math-container">$B$</span> the branching factor, but IDS requires less memory, typically <span class="math-container">$O(P)$</span>, while BFS uses <span class="math-container">$O(B^P)$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-12T09:17:24.190Z
Answers.LastActivityDate: 2021-12-21T00:03:26.787Z
Answers.LastEditDate: 2021-12-21T00:03:26.787Z
Answers.UserDisplayName: salva
Answers.Body: <p>If your search tree's branching factor is finite but its depth is unbounded, then DFS isn't "complete". What that means is that it may not ever find the goal node even if it exists. You would use these techniques precisely when this situation arises.</p>
  
  <p>To understand this, let's say you're at the node A in the following tree:</p>
  
  <pre><code>     A
      / \
     /   \
    B     C
   / \   / \
  .   . .   .
  </code></pre>
  
  <p>You choose to explore subtree rooted at B. Now if there are no goal nodes in that subtree, but the goal nodes were in the subtree rooted at C, then we're stuck. Because  we will keep searching there because we don't know beforehand that there are no goal nodes there, next node we explore could always be a goal node. But this essentially means that we'll never finish searching the subtree rooted at B in finite time, and never backtrack to explore the subtree rooted at C.</p>
  
  <p>So to overcome this you would want to iterative deepening depth-first search or depth-limited search.</p>
  
  <p>In <strong>depth-limited search</strong> you set a limit on the depth you'll explore. Let's say you choose <span class="math-container">$d$</span> as the depth limit because you know that the solution lies within that depth limit.</p>
  
  <p>And let's say the branching factor for your tree is <span class="math-container">$b$</span>. Going back to our example, you have finite elements in the subtree rooted at B (at most <span class="math-container">$b^d$</span>, can you reason why?), so we'll be able to look at all of them and eventually backtrack and start exploring subtree rooted at C, and we'll be able to find our answer. </p>
  
  <p>Now if you don't know the depth <span class="math-container">$d$</span> which goal nodes lie at, then you'll use <strong>iterative deepening</strong> DFS, which essentially does depth limited search but keeps increasing the value of <span class="math-container">$d$</span> on each iteration, so you're guaranteed to find a goal node, if it exists.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-12T08:09:00.730Z
Answers.LastActivityDate: 2018-12-12T13:51:09.003Z
Answers.LastEditDate: 2018-12-12T13:51:09.003Z
Answers.UserDisplayName: Peeyush Kushwaha
Body: <p>When should the iterative deepening search (IDS), also called iterative deepening depth-first search (IDDFS), and the depth-limited search be used?</p>
  
Tags: <applications><search><iddfs>
Title: When should the iterative deepening search and the depth-limited search be used?
UserDisplayName: Iram Shah
ThreadText: # When should the iterative deepening search and the depth-limited search be used?
  
  (Asked by: username_0 on 2018-11-02)
  
  When should the iterative deepening search (IDS), also called iterative deepening depth-first search (IDDFS), and the depth-limited search be used?
  
  **Tags:** applications, search, iddfs
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2018-12-12. Score: 2
  
  In practice, you can consider that IDS is a cheap way to implement a breadth-first search (BFS).
  
  When the branching factor is high, both algorithms have similar computational costs $O(B^P)$, where $P$ is the length of the solution path and $B$ the branching factor, but IDS requires less memory, typically $O(P)$, while BFS uses $O(B^P)$.
  
  
  ---
  
  ### Answer by username_2 on 2018-12-12. Score: 2
  
  If your search tree's branching factor is finite but its depth is unbounded, then DFS isn't "complete". What that means is that it may not ever find the goal node even if it exists. You would use these techniques precisely when this situation arises.
  To understand this, let's say you're at the node A in the following tree:
       A
      / \
     /   \
    B     C
   / \   / \
  .   . .   .
  
  You choose to explore subtree rooted at B. Now if there are no goal nodes in that subtree, but the goal nodes were in the subtree rooted at C, then we're stuck. Because  we will keep searching there because we don't know beforehand that there are no goal nodes there, next node we explore could always be a goal node. But this essentially means that we'll never finish searching the subtree rooted at B in finite time, and never backtrack to explore the subtree rooted at C.
  So to overcome this you would want to iterative deepening depth-first search or depth-limited search.
  In depth-limited search you set a limit on the depth you'll explore. Let's say you choose $d$ as the depth limit because you know that the solution lies within that depth limit.
  And let's say the branching factor for your tree is $b$. Going back to our example, you have finite elements in the subtree rooted at B (at most $b^d$, can you reason why?), so we'll be able to look at all of them and eventually backtrack and start exploring subtree rooted at C, and we'll be able to find our answer. 
  Now if you don't know the depth $d$ which goal nodes lie at, then you'll use iterative deepening DFS, which essentially does depth limited search but keeps increasing the value of $d$ on each iteration, so you're guaranteed to find a goal node, if it exists.
  
  
  ---
  
  