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 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 [777].

Steven M LaValle 2012-04-20