Week 3 — Heuristic Search

The smartest way to find the shortest path — explained so simply you'll never forget it

  1. A* Search Algorithm

    The smartest way to find the shortest path — explained so simply you'll never forget it

  2. Weighted A* Search (WA*)

    A* with inflated heuristics — faster but suboptimal, with bounded error

  3. SSS* Algorithm

    Best-first search for game trees — explores fewer nodes than alpha-beta by being smarter about which branches to pursue

  4. Traveling Salesperson Problem (TSP)

    The most famous NP-hard optimization problem — visit every city exactly once at minimum cost

  5. Branch and Bound (BnB)

    The exact method that prunes impossible branches — guaranteed optimal, exponential worst case but fast in practice

  6. Dijkstra's Algorithm

    The classic shortest-path algorithm — Branch & Bound made elegant. A* with zero intuition, and still guaranteed optimal

  7. SMA* — Simplified Memory-Bounded A*

    A* that fits in whatever memory you have — forgets the worst leaf, remembers the best forgotten path

  8. Which Algorithms Guarantee the Optimal Path?

    The multi-select question that reappears in nearly every paper — one table to answer them all

  9. Best First Search

    The pure heuristic search — follow the gradient downhill, no cost awareness. The precursor to A* and the foil to Dijkstra