Iterative deepening depth-first search

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a <a href="/facts/State_space_search/bky9oQSb">state space</a>/graph search strategy in which a depth-limited version of <a href="/facts/Depth-first_search/luxJKVph">depth-first search</a> is run repeatedly with increasing depth limits until the goal is found. IDDFS is optimal, meaning that it finds the shallowest goal. Since it visits all the <a href="/facts/Node_(computer_science)/eYlvVE0z">nodes</a> in the <a href="/facts/Search_tree/zJIIMEH8">search tree</a> down to depth 
  
    
      
        d
      
    
    {\displaystyle d}
  
 before visiting any nodes at depth 
  
    
      
        d
        +
        1
      
    
    {\displaystyle d+1}
  
, the cumulative order in which nodes are first visited is effectively the same as in <a href="/facts/Breadth-first_search/2kulDXCx">breadth-first search</a>. However, IDDFS uses much less memory.
</p>

Iterative deepening depth-first search open-in-new

Iterative deepening depth-first search