Q2 — SEARCH FOR OPTIMAL SOLUTION

DFID is provably optimal only because every iteration re-inspects nodes it closed in earlier iterations.

The Question

#	Question	Official answer
2	Under what cases does Depth First Iterative Deepening (DFID) guarantee an optimal solution?	C

The Topic in 60 Seconds

DFID runs a depth-limited DFS with limit $1, 2, 3, \dots$ Each iteration throws away all bookkeeping from the previous one and starts from scratch. With unit edge costs, the iteration with limit $d$ visits every node at depth $\le d$ as if it were brand new, so the first iteration that reaches the goal reaches it at minimum depth — exactly what BFS would return, at DFS memory cost.

Deep-dive: browse the Concepts section for iterative deepening.

Solutions

2 — Under what cases does Depth First Iterative Deepening (DFID) guarantee an optimal solution?

Options:

Option	Verdict
A — When it inspects only new nodes	Fails: skipping previously seen nodes means an early iteration could close a node on a shallow path and later iterations would refuse to walk through it
B — When it inspects new as well as open nodes	Not the guarantee: OPEN-only reuse still lets stale frontier entries block rediscovery; DFID keeps no cross-iteration frontier at all
C — When it inspects new as well as closed nodes	Correct — see below
D — None of these	Wrong: C is exactly the case

Answer: C

Why C is right

The optimality argument lives in the redundant work. On iteration with limit $d$ , DFID re-generates and re-expands every node closed by iterations $1 \dots d-1$ — nothing is remembered. That is precisely what makes it safe:

Suppose a goal $g$ sits at depth $k$ (fewest moves, unit costs).
Iterations $1 \dots k-1$ never reach depth $k$ , so they cannot report $g$ .
Iteration $k$ explores all paths of length $\le k$ from scratch — closed-node history from earlier rounds is discarded, so nothing blocks reaching $g$ via its shortest route.
Hence the first success happens at depth exactly $k$ : shortest path guaranteed.

If DFID did respect old CLOSED nodes (option A's spirit inverted / a global closed list), a node first closed at depth $j$ in a small iteration would never be re-expanded, and a strictly shorter route found only at limit $d > j$ could be missed — optimality breaks. DFID's apparent wastefulness (re-expanding closed nodes over and over) is not a bug; it is the optimality proof.

Tricks & Tips

Answers: 2 C