A state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found.

An example: Order in which the nodes are expanded

Properties:

  • Completeness: yes, for finite
  • Optimality (Admissibility): yes, for equivalent cost steps 
  • Time Complexity: O(bd)
  • Space Complexity: O(bd), b – branching factor, d – depth