Iterative Deepening Depth-First Search

Iterative deepening search, or more specifically iterative deepening depth-first search, is a state space and graph search strategy that runs a depth-limited depth-first search repeatedly with an increasing depth limit until the goal is found. It is optimal, meaning it finds the shallowest goal, and because it visits every node down to depth d before visiting any node at depth d+1, its cumulative visiting order is effectively the same as breadth-first search, while using much less memory than breadth-first search does.