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	Which of the following variants of Depth First Iterative Deepening (DFID) is guaranteed to find an optimal solution?	C

The Topic in 60 Seconds

DFID runs depth-limited DFS with limit $1, 2, 3, \dots$ , throwing away all bookkeeping between iterations. With unit edge costs, the iteration with limit $d$ re-explores every node at depth $\le d$ from scratch — so the first iteration that reaches the goal reaches it at minimum depth. BFS optimality at DFS memory cost.

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

Solutions

2 — Which DFID variant guarantees an optimal solution?

Options:

Option	Verdict
A — inspects only new nodes	Fails: skipping previously seen nodes lets an early iteration close a node on the shallow path; later iterations refuse to walk through it
B — inspects new as well as open nodes	Not enough: reusing stale OPEN entries can still block rediscovery; textbook DFID keeps no cross-iteration frontier at all
C — 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:

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

If DFID respected old CLOSED entries (the spirit of A), a node first closed at depth $j$ would never be re-expanded, and a strictly shorter route discovered only later could be missed. DFID's wastefulness (re-expanding closed nodes every iteration) is not a bug — it is the optimality proof.

Tricks & Tips

Answers: 2 C