Iterative Deepening Search (IDS)

The idea

Iterative Deepening Search (IDS) is an uninformed search: it uses no clues about which direction the goal is in, it just explores. It runs a depth-limited search over and over, allowing depth 0 first, then depth 1, then depth 2, and so on, restarting from the start each time. Each round digs one level deeper until the goal appears. This clever trick gives it the shallow-goal-first behavior of BFS while using only the tiny memory of DFS.

How it works

1. Set a depth limit L = 0 (you're only allowed to look at the start node itself this round).
2. Run a Depth-Limited Search (DFS that refuses to go deeper than L): put the start node on OPEN.
3. Pop a node from OPEN, move it to CLOSED (it's now expanded/visited for this round), and check if it's the goal — if yes, stop and report success.
4. If the popped node is still shallower than L, expand it: push its children onto OPEN to explore deeper.
5. Keep going until OPEN is empty (this round found nothing within depth L).
6. Increase the limit: L = L + 1, and importantly throw away CLOSED and OPEN so you start fresh from the root.
7. Repeat the whole depth-limited search with the new, deeper limit.
8. Because the limit grows 0, 1, 2, 3..., the first time you reach the goal it is at the shallowest possible depth — the fewest steps away.

See it step by step

Watch Iterative Deepening 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

← Prev Step 1 / 21 Next step →

OPEN, CLOSED & the data structures

OPEN (the frontier of nodes waiting to be expanded) is a stack (last-in, first-out), which is what makes each round behave like depth-first search — you dive down a branch before trying siblings. CLOSED (the already-expanded/visited nodes) tracks what you've handled so you don't re-process the same node within a single round. Both OPEN and CLOSED are reset to empty at the start of every new depth limit, because IDS deliberately re-explores the shallow nodes from scratch each time.

Pseudocode

function IDS(start, goal):
    for limit = 0, 1, 2, 3, ...:          # try ever-deeper limits
        result = DLS(start, goal, limit)  # fresh search each round
        if result == FOUND:
            return SUCCESS                 # goal at shallowest depth

function DLS(start, goal, limit):
    OPEN  = stack containing (start, depth=0)
    CLOSED = empty set
    while OPEN not empty:
        (node, depth) = OPEN.pop()
        if node == goal: return FOUND
        add node to CLOSED
        if depth < limit:                  # allowed to go deeper?
            for each child of node:
                if child not in CLOSED:
                    OPEN.push((child, depth + 1))
    return NOT_FOUND                        # nothing within this limit

At a glance