Q3 — SEARCH FOR OPTIMAL SOLUTION
When the whole search space cannot sit in memory, SMGS is the only listed algorithm whose optimality proof survives the memory cut.
The Question
| # | Question | Official answer |
|---|---|---|
| 3 | Given a state space (and a search space) that is too large to fit into main memory, and with Euclidean edge costs, and with the best admissible heuristics, which of the following algorithms will you choose to find an optimal path? | G |
The Topic in 60 Seconds
Three constraints stack up here: (1) memory is smaller than the space, (2) costs are non-uniform (Euclidean), (3) is admissible. The algorithm must stay optimal while respecting the memory bound — that pair of demands eliminates six of the seven options.
Deep-dive: browse the Concepts section for memory-bounded search.
Solutions
3 — Too-large-for-memory space, Euclidean costs, best admissible heuristics. Which algorithm?
| Option | Verdict |
|---|---|
| A — Depth First Search | No: fits memory but ignores costs entirely — never optimal with non-uniform edges |
| B — Breadth First Search | No: needs the whole level in memory AND minimises edge-count, not Euclidean cost |
| C — Dijkstra | No (here): optimal, but its OPEN/CLOSED grow to the size of the space — dies on the memory constraint |
| D — Branch and Bound | No (here): same disease as Dijkstra; the bound list itself outgrows memory |
| E — A* | No (here): optimal given admissible , but stores every generated node — blows the memory budget |
| F — WA* for some w | No: bounded-suboptimal at best (), and still memory-hungry |
| G — SMGS | Correct: Sparse Memory Graph Search provably returns optimal paths while keeping only a sparse subset of the graph in memory |
Answer: G
Why only G survives all three constraints
| Constraint | Kills | Survived by |
|---|---|---|
| Space > memory | B, C, D, E (all keep ~full OPEN/CLOSED) | A (tiny memory, but…), G |
| Non-uniform costs | A (ignores costs), B (counts edges) | C, D, E, F, G |
| Optimality required | F (only w·C*-bounded) | C, D, E, G |
Intersecting the surviving columns leaves exactly one name: SMGS. Its trick is deliberate node pruning + regeneration: it forgets nodes it can provably re-derive later, so the memory bound holds without giving up the admissible- optimality argument.
Tricks & Tips
Answers: 3 G