Uninformed search

Depth-Limited Search (DLS)

DFS with a leash — explore deep, but never past the fence.

On the Sydney → London problem, Depth-Limited Search finds: Sydney → Colombo → Istanbul → London — total 23.5h.

The idea

Depth-Limited Search (DLS) is plain Depth-First Search with one extra rule: a hard depth cap called L. It explores a path as deeply as it can, but the moment it reaches depth L it refuses to go any deeper and backtracks. That single cap fixes DFS's worst flaw — getting lost forever down an endless branch — because DLS is guaranteed to stop. It is an uninformed search: it uses no hints about where the goal might be.

How it works

Start with only the start node on OPEN (the frontier), tagged with depth 0. Pick a limit L before you begin.
Take the most recently added node off OPEN (that's the 'depth-first' part — newest first, like a stack) and move it to CLOSED as expanded.
If this node is the goal, stop and report success.
Check its depth. If its depth equals L, do NOT generate any children — this branch has hit the fence, so just backtrack to the next node on OPEN.
If its depth is below L, generate its children, give each child a depth of parent-depth + 1, and add them to OPEN.
Repeat: always pull the newest node from OPEN, expand or cut off by depth, until OPEN is empty.
If OPEN empties without finding the goal, report failure — the goal was either absent or sitting deeper than L.

See it step by step

Watch Depth-Limited Search search a real problem — flying from Sydney (SYD) to London (LHR). Click Next to advance one expansion and watch OPEN, the traversal, the path and the cost update live.

Start at Sydney. OPEN (the frontier) holds just Sydney.

Expanding

OPEN — frontier

CLOSED — traversal

Path so far

Cost so far

Step 1 / 5

OPEN, CLOSED & the data structures

OPEN is the frontier of discovered-but-not-yet-expanded nodes, and here it behaves as a stack (LIFO): we always expand the most recently added node, which is what drives us deep before wide. Each node on OPEN carries its depth so we can enforce the limit L. CLOSED holds the nodes we have already expanded; it records what we've visited so we can trace the path and, in graph versions, avoid re-expanding the same node.

Pseudocode

function DLS(start, goal, L):
    OPEN  = stack containing (start, depth = 0)
    CLOSED = empty set

    while OPEN is not empty:
        (node, depth) = OPEN.pop()        # newest first -> depth-first
        add node to CLOSED                 # mark as expanded/visited

        if node == goal:
            return success (reconstruct path)

        if depth < L:                      # only expand above the cap
            for each child of node:
                if child not in CLOSED:
                    OPEN.push((child, depth + 1))
        # if depth == L: do nothing -> backtrack (respect the fence)

    return failure                          # goal absent or deeper than L

At a glance

Complete?Only sometimes — complete when the goal sits at depth <= L; if it's deeper, DLS declares failure even though a solution exists.

Optimal?No — it returns the first goal DFS stumbles into within the limit, which may be far from the shallowest or cheapest one.

TimeO(b^L), where b is the branching factor and L is the depth limit — the cap bounds the work regardless of how deep the tree really goes.

SpaceO(b*L) — like DFS, it only stores the current path plus each node's unexpanded siblings, so memory grows with the limit, not the whole tree.

👍 When to use it

You know (or can safely guess) roughly how deep the goal is, so you can pick a good L.
You need DFS's tiny memory footprint but must guarantee the search actually stops.
The graph is huge or possibly infinite and plain DFS would run away forever.
As the building block inside Iterative Deepening Search, which retries DLS with L = 0, 1, 2, ... to regain completeness.

⚠️ Watch out for

Picking L too small makes DLS miss a goal that truly exists — 'failure' can mean 'not found within L,' not 'no solution at all.'
Picking L too large brings back DFS's cost and wasted effort, doing lots of deep exploration for nothing.
It is not optimal: the first goal found within L may be deeper or costlier than another goal you'd prefer.
On graphs with cycles, skipping the CLOSED check lets you loop within the limit and re-expand nodes — always check CLOSED (or track the path) to avoid revisiting.

Now see it for yourself

Open Depth-Limited Search in the visualizer — step through it, pause, and watch OPEN & CLOSED change.

▶ Watch it run