iterative deepening

what is iterative deepening

• Idea: get DFS’s space advantage with BFS’s time / shallow-solution advantages
• Run a DFS with increasing depth limit
• Not wastefully redundant, most work in lowest level
• Properties:
  • Time complexity: $$\begin{gathered} (O(b^s) \\ ) \end{gathered}$$
  • Space complexity: $$\begin{gathered} (O(bs) \\ ) \end{gathered}$$
  • Complete: yes
  • Optimal: only if costs are all 1
• visualization