iterative deepening

A graph search algorithm. When searching for a path through a

graph from a given initial node to a solution node with some

desired property, a {depth-first search} may never find a

solution if it enters a cycle in the graph. We can either add

an explicit check for cycles so that we never extend a path

with a node it already contains or we can use iterative

deepening where we explore all paths up to length (or "depth")

N, starting from N◦0 and increasing N until a solution is

found.

(1995-02-14)