Iterative deepening

The iterative deepening approach is usually preferable if the search tree has a large branching factor (i.e., there are many more vertices in the next level than in the current level). This could occur if there are many actions per state and only a few states are revisited. The idea is to use depth-first search and find all states that are distance $i$ or less from ${x_{I}}$. If the goal is not found, then the previous work is discarded, and depth first is applied to find all states of distance $i+1$ or less from ${x_{I}}$. This generally iterates from $i=1$ and proceeds indefinitely until the goal is found. Iterative deepening can be viewed as a way of converting depth-first search into a systematic search method. The motivation for discarding the work of previous iterations is that the number of states reached for $i+1$ is expected to far exceed (e.g., by a factor of $10$) the number reached for $i$. Therefore, once the commitment has been made to reach level $i+1$, the cost of all previous iterations is negligible.

The iterative deepening method has better worst-case performance than breadth-first search for many problems. Furthermore, the space requirements are reduced because the queue in breadth-first search is usually much larger than for depth-first search. If the nearest goal state is $i$ steps from ${x_{I}}$, breadth-first search in the worst case might reach nearly all states of distance $i+1$ before terminating successfully. This occurs each time a state $x \not \in {X_{G}}$ of distance $i$ from ${x_{I}}$ is reached because all new states that can be reached in one step are placed onto ${Q}$. The $A^*$ idea can be combined with iterative deepening to yield $IDA^*$, in which $i$ is replaced by $C^*(x') + \hat{G}^*(x')$. In each iteration of $IDA^*$, the allowed total cost gradually increases [777].