Q2 — Search Algorithms Theory

DFID's closed-list secret, the two survivors of an unknown heuristic under arbitrary costs, and why w = 0 turns wA* into Dijkstra.

The Question

#	Question	Official answer
2.1	Which of the following variants of Depth First Iterative Deepening (DFID) is guaranteed to find the shortest path if one exists?	C
2.2	Given a finite state space with edge costs that may or may not be Euclidean and a heuristic function whose properties are not known, which of the following algorithms are suitable for finding the optimal path?	C, D
2.3	If w is set to zero then wA* algorithm will __________ .	B, C

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

Solutions

2.1 — DFID optimality → C

DFID re-runs depth-limited DFS with limits $1, 2, 3, \dots$ , discarding bookkeeping between rounds. The optimality proof lives in that amnesia: iteration $k$ re-inspects every closed node from earlier rounds, so nothing blocks the shallowest goal when its depth arrives.

A (new nodes only): an early round could close a node on the shallow path — later rounds refuse to reuse it ✗
B (new + open): stale frontier entries still block rediscovery ✗
C (new + closed): correct ✓
D: contradicted by C ✗

2.2 — Arbitrary costs + unknown $h$ → C, D

Two filters, applied in order:

Unknown $h$ removes every heuristic-trusting method: A*, WA*, SMGS.
Non-uniform costs ("may or may not be Euclidean") removes BFS (fewest edges ≠ cheapest) and already removed DFS.

Survivors: Dijkstra (C) and Branch-and-Bound (D) — both order by true accumulated cost and consult no heuristic.

2.3 — $w = 0$ → B, C

$f(n) = g(n) + 0 \cdot h(n) = g(n)$

Ordering collapses to pure accumulated cost:

B ✓: this is exactly Dijkstra's algorithm — expansion by cheapest $g$ .
C ✓: optimality is guaranteed (it is Dijkstra); the conditional "if $h$ is admissible" is satisfied vacuously — the guarantee holds regardless of $h$ .
Best-first behaviour needs $w \to \infty$ , not $w \to 0$ ✗; "no guarantee" claims contradict Dijkstra's theorem ✗.

Memorise the dial: $w = 0$ → Dijkstra · $w = 1$ → A* · $w > 1$ → bounded-suboptimal · $w \to \infty$ → greedy Best-First.

Tricks & Tips

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