Iterative deepening search

Iterative deepening search (IDS) is a searching algorithm that aims to be a middle-ground uninformed search algorithm between DFS and BFS. The main idea is that we perform DFS with a depth limit $l$, and iteratively increase $l$ until we find a solution. i.e., for a given depth limit $l$, if we can’t find a solution with DFS, then we try again with a depth limit $l+1$.

This gives us the benefits of both algorithms.

• We get BFS’ termination guarantee, at level $d$ if a solution exists. We also avoid DFS’ possibility of looping infinitely.
• We get a length-optimal solution, but not a cost-optimal solution.
• The space complexity is the same as DFS, $\mathcal{O}(bd)$.
• The time complexity is the same as BFS, $\mathcal{O}(b^d)$.

A-star

Iterative deepening A-star uses a similar iteratively increasing limit until we find a solution. Instead of the depth limit, we iteratively increase the minimum $f$-value (i.e., cost + heuristic). This reduces the memory requirements for A*, since we can maintain only linear space.

Note that we perform a DFS (not A-star?) and only cut off the branch when the total cost exceeds our threshold. So we also avoid the overhead of maintaining a priority queue.