Iterative Deepening search is general strategy often used in combination with DFS, that finds the best depth limit. It does this by gradually increasing the limit first 0, then 1, then 2, and so on. Until goal is found. This will occur when the depth limit reaches d, the depth of the shallowest goal node. The algo is shown in figure (10).

Figure (10) The Iterative Deepening search algo, which repeatedly applies DLS with increasing limit. It terminates when a solution is found or if the depth limited search returns failure, meaning that no solution exists.

Iterative Deepening combines the benefits of depth – first and breadth – first search. Like DFS, its memory requirements are very modest I O(bd) to be precise. Like BFS, it is complete when the branching factor is finite and optimal when the depth cost is a non decreasing function of the depth of the node. Figure (11) shows four iterations of IDS on a binary search tree where the solution is found on the fourth iteration.

Fig (11) IDS on a Binary Tree.

Iterative deepening search may seem wasteful because states are generated multiple times. In an IDS, the nodes on bottom level (depth d) are generate once, those on the next to bottom level are generated twice and so on. Up to the children of the root which are generated d times. So, the total nodes generated is,

$N(IDS) = (d)b + (d-1) b^2 + . . . + (1) b^d$

Which gives time complexity of $O (b^d)$

We can compare this to the node generated by a BFS.

$N(BFS) = b + b^2 + . . . + b^d + (b^{d+1} – b)$

It means that BFS generates same nodes at depth d + 1, whereas IDS does not. The result is that IDS is actually faster than BFS.

Example: If b = 10, and d = 5.

N(IDS) = 50 + 400 + 3000 + 20,000 + 100,000 = 123,450

N(BFS) = 10,000 = 1000 + 10,000 + 100,000 + 999,990 = 1,111,100

In general, IDS is the preferred uninformed search method when there is a large search space and the depth of the solution is not known.