Pattern Database Heuristics
What you'll learn: How precomputed lookup tables can deliver powerful, admissible heuristics for complex search problems by storing exact solution costs for simplified subproblems.
The Core Idea
Instead of computing heuristic estimates on-the-fly during A* search, pattern databases solve simplified versions of your problem once beforehand and store all solution costs in a lookup table. When you need a heuristic during search, you just look up the answer—fast and still admissible!
How It Works
Pattern databases focus on a subset of the problem's components. For example, in a 15-puzzle, instead of tracking all 16 tiles, you might only care about tiles 1–6. You solve this relaxed problem exhaustively from every possible configuration of those tiles, storing the optimal cost to reach the goal pattern.
During A* search, you extract the pattern from your current state (ignoring irrelevant tiles) and look up the precomputed cost. Because you're solving a relaxed problem (fewer constraints), the stored cost never overestimates the true cost—making it admissible.
Why It's Powerful
- Accuracy: Pattern databases encode exact solutions to subproblems, often much better than simple distance metrics
- Speed: Lookup is O(1) once the database is built
- Composability: You can combine multiple pattern databases (e.g., one for tiles 1–6, another for tiles 7–12) using max or sum operations while preserving admissibility
Think of it like having a cheat sheet of "minimum moves needed" for common subconfigurations—you did the hard work once, offline, and now reap the benefits during every search.
Key Takeaway: Pattern database heuristics precompute and store optimal costs for simplified subproblems, providing fast, highly-informed, admissible heuristics that dramatically improve A* search performance on complex problems.