How does iterative deepening relate to this?

It repeatedly runs depth-limited searches with increasing bounds.

Does a finite limit always terminate?

It does under finite branching and terminating operations; an unbounded successor generator or stalled operation can defeat that expectation.

Does depth equal path cost?

Only under a suitable cost convention, such as one unit per transition. Otherwise they differ.

AI Glossary / Graphs and symbolic AI / Advanced

Depth-limited search

Definition

Depth-limited search is a search strategy that explores paths only up to a specified maximum depth, commonly using depth-first exploration within that boundary. The depth counts transitions from the starting state, usually assigned depth zero. A limit prevents the search from following a branch indefinitely, but it can also exclude deeper solutions.

What it means

A depth limit answers a bounded question: can a goal be reached within this many steps? It does not ordinarily answer whether the goal can be reached at any depth. Reporting the distinction is essential when a system uses bounded search to support a decision.
The limit concerns path length, not elapsed time, monetary cost, or the number of nodes examined. A shallow search can still contain many branches, and individual transitions can have very different costs.
Depth-limited search is useful when a meaningful bound is known or when it forms part of a broader strategy such as iterative deepening.

How it works

Start at depth zero and explore successors in depth-first order. A standard recursive version tests whether the current state is a goal before checking whether the remaining depth allowance is zero. This permits a goal exactly at the boundary to succeed. Non-goal boundary nodes are not expanded further.
The search distinguishes success, failure, and cutoff. Success returns a solution. Failure means the explored search has been exhausted without a solution or an unresolved depth cutoff. Cutoff indicates that the depth boundary prevented further exploration; a deeper solution may exist.
With finite branching and terminating successor generation, a finite depth limit produces a finite search. Cycle checks can reduce repeated work. A global visited set needs care: reaching a state through a long path must not incorrectly prevent exploring it later with more depth allowance.

Three practical examples

Workflow planning: A planner searches for a way to complete a request within four modeled actions. A cutoff means it has not established whether a longer workflow succeeds.
Puzzle solving: A solver investigates move sequences up to a chosen length. Increasing the bound may reveal a solution that was previously excluded. The first solution within a depth-first run is not necessarily the shortest among all permitted solutions.
Dependency exploration: An analyst inspects relationships up to three hops from an application. The result describes that bounded neighborhood rather than the full dependency graph. Missing a distant component does not prove it is unrelated.

Think of it this way

Imagine searching a branching building layout but allowing yourself to pass through at most two doors from the entrance. You can thoroughly inspect that bounded area while leaving deeper rooms unexplored. “Not found within two doors” is different from “not anywhere in the building.”

Worked example

Consider an invented search tree. Start S has children A and B, explored in that order. A has child C, and C has child G, the goal. B has child D, which is a dead end. There are no other edges.
The depths are S at zero; A and B at one; C and D at two; and G at three. With limit two, a standard recursive depth-limited search visits S, A, C, B, and D but does not expand C to reach G. It reports cutoff rather than a solution.
With limit three, the same ordering visits S, A, C, and G, then succeeds. The returned path has three transitions. G is accepted at the boundary because the goal test occurs before the zero-allowance cutoff test.
Now consider a different tree where S leads only to A, and A is a non-goal dead end. With limit three, this entire tree is exhausted before the boundary, so the result is failure rather than cutoff.
For scale, a full binary tree through depth three contains 1 + 2 + 4 + 8 = 15 nodes. Through depth four it contains 31. Thus adding one depth level can substantially increase work even though the numeric limit changes only slightly.

Illustrative case study

Fictional Cedar Planning evaluates a tool that searches for short internal workflows. Its interface initially reports “impossible” whenever no solution is returned. Reviewers discover that the tool sometimes stopped because its configured step limit was reached.
The team separates three outcomes in the report: a plan found, a bounded search cut off, and the modeled search space exhausted without a plan. It records the limit and tests a known solution lying exactly on the boundary, plus another one just beyond it.
The revised wording makes the search result more interpretable, but it does not prove that the workflow model fully represents real constraints. This case is illustrative, not a measured deployment result.

Common misconceptions and mistakes

“Cutoff proves no solution exists.” It leaves deeper possibilities unresolved.
“A depth limit is a time limit.” Branching and operation costs also determine runtime.
“A goal at the boundary must fail.” Standard goal-first checking permits it.
“The first solution is always shortest.” Depth-first ordering can find a deeper solution before a shallower one on another branch.
“Visited-state handling is identical to unrestricted graph search.” Remaining depth can affect what is still reachable from a repeated state.

Business use

Define the limit in terms meaningful to the task, such as transitions, moves, or dependency hops. Explain the result's scope and retain cutoff as a distinct status. If the application needs an unbounded impossibility claim, a bounded unsuccessful run alone is insufficient evidence.
Test boundary behavior and repeated states reached at different depths. Measure work as well as depth, because branching can make apparently small bounds expensive. Decide whether a cutoff should trigger a larger limit, a different search method, or a clearly qualified result.

Check your understanding

Why does limit two miss G?

Answer: G lies at depth three.

Why can limit three accept G?

Answer: Goal testing includes the boundary state.

What does cutoff justify saying?

Answer: No solution was found within the completed bounded exploration, while deeper possibilities remain unresolved.

Related terms

Depth First Search
Branching factor
Completeness
Graph search
iterative deepening
cutoff
search depth
path cost

Learn next

Trace one tree with a goal at the limit and another with a goal just beyond it. Record success, failure, and cutoff separately. Then add a repeated state reached by paths of different lengths and inspect the remaining allowances.

Repeated state

Sources

AIMA Java, DepthLimitedSearch, recursive algorithm and return outcomes: https://aimacode.github.io/aima-java/aima3e/javadoc/aima-core/aima/core/search/uninformed/DepthLimitedSearch.html Russell and Norvig, search slides, depth-limited search and iterative deepening: https://aima.eecs.berkeley.edu/2nd-ed/slides-pdf/chapter03.pdf

Previous: Depth image Next: Depth map