iterative deepening

views updated

iterative deepening A technique used to enhance depth-first search. The search tree is first processed to a maximum depth of two, and then the whole process is repeated to a depth of three, then again to four, and so on to the maximum depth n. Surprisingly, this costs little more than a single search to depth n (due to the exponential growth rate of the branching factor) and guarantees to find a shortest path to the solution. See also combinatorial explosion.