SMGS and Frontier Search — Memory-Bounded Optimal Search

When A* won't fit in memory — keep only the frontier, use relay layers, and stay optimal. The exam's favorite answer for 'large space + best admissible heuristic'

The Simplest Explanation

A* is optimal but stores everything ( $O(b^d)$ ). When the state space won't fit in RAM:

Frontier Search (Korf & Zhang) keeps only the boundary between Open and Closed
SMGS (Sparse Memory Graph Search, Zhou & Hansen) adds relay layers only when needed
IDA* keeps nothing beyond the current path (DFS)

The exam's trick question: "State space too large for memory, Euclidean costs, best admissible heuristics — which algorithm for optimal path?" Answer: SMGS (G).

Remember This

Large space + need optimal + best heuristics → SMGS. Small space → A*. No heuristic knowledge → Dijkstra/B&B.

Why A* Explodes

For sequence alignment (Week 6 Lecture 65): grid $(n+1) × (m+1)$ , Open grows $O(n)$ , but Closed grows $O(n×m)$ — quadratically! Deleting Closed is where big savings lie.

Frontier Search

Idea: Partition Closed into Kernel (all neighbors Closed — interior) and Boundary (neighbors Open — edge). Delete Kernel, keep Boundary + Open.

How to prevent leaking back into deleted territory? Store a taboo list on each Open node's neighbors.

Path reconstruction: Without full Closed, you lost parent pointers. Solution: relay nodes — save a middle layer where $g≈h$ (halfway). When goal found, recursively solve start→relay and relay→goal (divide & conquer). Cost: $O(d·T(d))$ time for $O$ space savings.

SMGS (Adoptive Relay)

Frontier Search always creates relays at midpoints. SMGS is lazier: monitor memory, only create a relay layer when RAM is low. If problem fits, it's just A*.

Start as A*
When memory pressure → convert current Boundary → relay layer, delete Kernel
Continue; may create multiple relays
Maintains three sets: Open, Boundary, Kernel

This adaptivity makes SMGS the practical choice — it uses all available memory before paying relay overhead.

Comparison: Memory-Bounded Optimal Algorithms

Algorithm	Space	Optimal?	Key Idea
A*	$O(b^d)$	Yes	Keep everything
IDA* (Korf 1985)	$O(d)$	Yes	DFS with $f$ -cutoff iteratively deepened
RBFS (Korf 1991)	$O(d)$	Yes	Best-first with backtracking & thrashing
Frontier Search	$O(bd)$ frontier	Yes	Delete Kernel, taboo lists
SMGS	Adaptive $O$	Yes	Frontier + on-demand relays
SMA*	$O(m)$ bounded	Only if $m$ ≥ solution depth	Forget worst leaf, backup $f$
Beam Search	$O(Wd)$	No	Keep $W$ best per level

IDA* vs RBFS (Quick)

IDA*: cutoff = $f(start)$ , DFS pruning $f>$ cutoff, next cutoff = min pruned $f$ . Linear space, admissible, but repeated search hurts when many nodes share same $f$ (cutoff grows slowly).

RBFS: Explore best child, remember second-best $f$ ; if all children exceed second-best, rollback and backup best child $f$ to parent. Also linear space but thrashing when branches tie.

Exam Patterns

Q: "Too large for memory, Euclidean, best admissible heuristics" → SMGS
Q: "Unit costs, heuristic unknown, want optimal" → BFS, Dijkstra, B&B (not A*/SMGS because unknown h)
Q: "Euclidean + best admissible" → Dijkstra, B&B, A, SMGS* (all optimal)
Q: "Weighted A* w large → behaves like?" → Best First (not optimal even if $h$ admissible)

QuizWhen would you choose SMGS over A*?

QuizFrontier Search deletes Kernel nodes. How does it prevent returning to deleted space?

QuizIDA*'s main downside vs A* is...