Course contentsShow
← Computer Science
Lesson 2758 of 2,87261. AI and Search AlgorithmsFree lesson

Pattern Database Heuristics

Learn how precomputed pattern databases provide powerful admissible heuristics for complex problems.

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.