Q2 — Search Algorithms Theory

Three guarantee questions: DFID's closed-list secret, which algorithms survive an unknown heuristic, and why wA* at infinity forgets g entirely.

The Question

Answer the given subquestions.

#	Question	Official answer
2.1	Under what cases does Depth First Iterative Deepening (DFID) guarantee to find the shortest path if one exists?	C
2.2	Given a finite state space with unit edge costs, and a heuristic function whose properties are not known, which of the following algorithms are suitable for ...	B, C, D
2.3	If w is set to a large value (tending to infinity) then wA* algorithm will __________ .	A, D

The Topic in 60 Seconds

Guarantees attach to assumptions: DFID needs unit costs + amnesia about CLOSED; heuristic methods need admissibility — unknown $h$ kills them; $f = g + w\cdot h$ degenerates to pure $h$ -greed as $w \to \infty$ .

Deep-dive: browse the Concepts section for optimal search.

Solutions

2.1 — DFID optimality → C

DFID re-runs depth-limited DFS with limit $1, 2, 3, \dots$ , discarding all bookkeeping between rounds. Optimality lives in the amnesia: iteration $k$ re-expands every node closed by iterations $1..k{-}1$ from scratch, so nothing blocks the shallowest goal when its turn comes.

Option	Verdict
A — inspects only new nodes	Fails: an early round could close a node ON the shallow path; later rounds refuse to reuse it
B — new + open	Not the guarantee: stale frontier entries still block rediscovery
C — new + closed	Correct: re-inspecting closed nodes every iteration is precisely the optimality proof
D — none	Wrong: C is textbook DFID

2.2 — Unknown-quality $h$ , unit costs → B, C, D

Split options into $h$ -users and $h$ -ignorers:

Option	Uses $h$ ?	Verdict
A — DFS	no, but ignores costs too	No: returns a goal, not the shallowest
B — BFS	no	Yes: unit costs make fewest-edges = cheapest
C — Dijkstra	no	Yes: cheapest-first expansion, no assumptions beyond non-negative costs
D — Branch & Bound	no	Yes: ranks by true accumulated $g$
E — A*	yes (admissibility)	No: unknown quality removes the guarantee
F — WA*	yes ( $w \cdot$ admissibility)	No
G — SMGS	yes	No: pruning rule safe only under admissible $h$

2.3 — $w \to \infty$ → A, D

$f(n) = g(n) + w \cdot h(n) \xrightarrow{w \to \infty} h(n)\ \text{dominates completely}$

A ✓: ordering collapses to $h$ alone = Best-First Search behaviour (greedy best-first).
B ✗: Dijkstra orders by $g$ — the exact opposite limit ( $w = 0$ ).
C ✗ / D ✓: even with admissible $h$ , ignoring $g$ means the first goal popped may sit down a cheap- $h$ but expensive- $g$ corridor — no optimality guarantee at any $w > 1$ , a fortiori at infinity.

Tricks & Tips

Answers: 2.1 C · 2.2 B, C, D · 2.3 A, D