Does iterative deepening need a heuristic?

Basic depth-based iterative deepening does not. Heuristic variants use additional information and different bounds.

Can it find a goal at the initial state?

Yes. The depth-zero iteration should test that state.

Does it always terminate when no solution exists?

Not on an infinite search space without an additional stopping condition. Completeness for a finite-depth goal is different from guaranteed termination on every unsolvable problem.

AI Glossary / Graphs and symbolic AI / Intermediate

Iterative deepening search

Definition

Iterative deepening search repeatedly performs depth-limited depth-first searches with increasing depth limits until it finds a goal or establishes failure. It combines shallowest-solution discovery with the relatively small memory requirements of depth-first exploration.

What it means

A depth-first search can pursue a long branch before checking a short solution elsewhere. Breadth-first search checks shallow levels first but can require a large stored frontier. Iterative deepening explores only to depth zero, then depth one, then depth two, and continues as needed.

Each iteration restarts from the initial state. This repeats work near the top of the search tree, but avoids retaining the entire growing frontier between iterations.

Depth counts actions or edges, not necessarily their total cost. Finding a solution at minimum depth gives a minimum-cost solution when all steps have the same positive cost. With unequal costs, the shallowest solution can be expensive. Cost-bounded methods such as IDA* use a different limiting criterion.

How it works

Run a depth-limited search with limit zero and test the initial state. If the search is cut off because deeper exploration may be needed, increase the limit and restart. At a given limit, use depth-first traversal while preventing expansion beyond that depth.

The search must distinguish a goal, a cutoff and genuine failure. A cutoff means the imposed limit stopped exploration; it does not prove that no solution exists. Exhausting the relevant finite search space without cutoffs can establish failure.

For a finite branching factor and a goal at finite depth, systematic iterative deepening eventually reaches that depth. Standard implementations store the current path and limited successor information rather than a complete breadth-first frontier. Handling cycles and repeated states requires care: a global visited set retained incorrectly across iterations can suppress paths that the deeper iteration needs to reconsider.

Three practical examples

A puzzle solver searches increasing move depths when the solution length is unknown and memory is limited.
A planning exercise looks for the fewest actions under a model where each action has the same cost.
A search demonstration contrasts repeated shallow exploration with the larger frontier retained by breadth-first search.

Think of it this way

Think of looking for an item by checking every nearby shelf, then restarting with permission to inspect one layer farther back, and gradually extending the reach.

The analogy captures progressively relaxed depth limits. Real search depth is a number of transitions in a model, not physical distance, and the method must still systematically explore every permitted branch at each limit.

Worked example

Counting repeated visits on a small tree

Suppose a search tree has exactly three children per non-leaf node through depth three. The root is at depth zero. There are 1, 3, 9 and 27 nodes at depths zero through three respectively. Place the only goal at the last node visited at depth three under a fixed traversal order.

With limit zero, iterative deepening visits one node. With limit one, it visits 1 + 3 = 4. With limit two, it visits 1 + 3 + 9 = 13. With limit three, it visits 1 + 3 + 9 + 27 = 40 before reaching the final goal.

Across the four iterations, the total is 1 + 4 + 13 + 40 = 58 node visits. There are only 40 distinct nodes, so 18 visits repeat earlier work. This calculation counts visits and goal checks under the stated convention, not only expanded internal nodes.

Breadth-first traversal would visit each of those 40 nodes once in this setup, but its frontier grows across levels. Iterative deepening instead trades repeated visits for lower retained search memory.

Now imagine a two-action solution costing 100 in total and a three-action solution costing 3. Iterative deepening by depth can return the two-action solution first. The example separates minimum action count from minimum total cost.

Illustrative case study

The fictional Willow Puzzles team develops a solver for a small symbolic puzzle. A breadth-first prototype finds short solutions but stores more frontier nodes than the available memory budget permits.

Reviewers test iterative deepening and record both peak retained nodes and total generated or visited nodes, defining those counters consistently. They include a no-solution finite case and a cycle case so that cutoff handling is not confused with failure.

Willow also documents that all puzzle moves have equal cost before describing the first result as cost-optimal. This fictional case illustrates choosing a search tradeoff and checking its assumptions, not a benchmark claim about a deployed solver.

Common misconceptions and mistakes

Restarting always makes iterative deepening impractical. In exponentially growing trees, the deepest level can dominate the work, limiting the relative overhead of earlier repetitions.
Minimum depth always means minimum cost. That requires appropriate cost assumptions.
Reaching a depth limit proves there is no solution. It usually indicates a cutoff that may justify another iteration.
Repeated states can be ignored without consequence. Cycles and duplicate paths affect both correctness precautions and practical work.

Business use

This strategy is useful when memory is a limiting resource, the solution depth is unknown and shallow solutions are meaningful. For branching factor b greater than one and solution depth d, the familiar tree-search time bound is O(b^d), while a standard depth-first implementation uses O(bd) memory.

These bounds describe a model of search, not guaranteed execution time on every application. A nearly linear chain has little exponential growth to absorb repeated work, and many paths to the same state can cause substantial duplication. Evaluate the actual search structure, action costs and duplicate-handling policy before selecting the method.

Check your understanding

In the worked tree, why are there 58 visits but only 40 distinct nodes?

Answer: Each iteration starts again at the root. Nodes above the final depth are visited in more than one iteration, adding 18 repeated visits.

Related terms

Learn next

Repeat the visit calculation for a binary tree through depth three with the goal last at that depth. Keep visits separate from distinct nodes, then compare the repeated-work fraction with the three-branch example.

Sources

AIMA's author algorithm collection specifies depth-limited and iterative deepening procedures: https://aima.eecs.berkeley.edu/algorithms.pdf

The author search slides discuss their properties and tradeoffs: https://aima.cs.berkeley.edu/4th-ed/slides-pdf/chapter03.pdf

Korf's original analysis studies depth-first iterative deepening: https://www.sciencedirect.com/science/article/abs/pii/0004370285900840

The tree counts and Willow Puzzles case are original illustrations. Complexity and optimality claims retain their stated assumptions.

Previous: Iteration Next: Iterative expansion