Week 6 — Memory-Bounded 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'

  1. 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'

  2. Sequence Alignment as Graph Search

    Aligning DNA strings is shortest-path search on a grid — the problem whose Closed list grows so fat it motivated frontier search

  3. Pruning OPEN — BFHS and Beam Stack Search

    Frontier search attacked Closed; this page attacks Open — upper bounds, breadth-first heuristic search, and the beam stack that can still backtrack

  4. The Monotone (Consistency) Condition

    The one inequality that lets A* never reopen a closed node — and the two consequences every exam trace relies on