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 or less from . If the goal is not found, then the previous work is discarded, and depth first is applied to find all states of distance or less from . This generally iterates from 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 is expected to far exceed (e.g., by a factor of ) the number reached for . Therefore, once the commitment has been made to reach level , 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 steps from , breadth-first search in the worst case might reach nearly all states of distance before terminating successfully. This occurs each time a state of distance from is reached because all new states that can be reached in one step are placed onto . The idea can be combined with iterative deepening to yield , in which is replaced by . In each iteration of , the allowed total cost gradually increases .
Steven M LaValle 2012-04-20