Generating admissible heuristics from sub problems: Pattern databases

 Pattern databases are a technique for generating admissible heuristics for search problems by precomputing the cost of reaching the goal state from all possible substates of the problem. They are particularly useful for problems with large state spaces, where computing an exact heuristic function for every state is infeasible.

The basic idea behind pattern databases is to partition the state space into smaller subspaces, or patterns, each of which can be solved independently using some other algorithm or heuristic function. The cost of reaching the goal state from each pattern is then precomputed and stored in a lookup table.

To use the pattern database as a heuristic function during search, the state is first partitioned into the corresponding patterns, and the precomputed costs for each pattern are looked up in the table. The sum of these costs provides an admissible estimate of the remaining cost to reach the goal state.

For example, consider the 8-puzzle problem, where the goal is to reach a particular configuration of tiles on a 3x3 grid. A pattern database for this problem might be constructed by partitioning the grid into three 2x2 subgrids, and precomputing the cost of reaching the goal state from each possible configuration of tiles within each subgrid.

During search, the current state is partitioned into the corresponding subgrids, and the precomputed costs for each subgrid are looked up in the table. The sum of these costs provides an admissible estimate of the remaining cost to reach the goal state.

Pattern databases can be combined with other heuristic functions to produce even more accurate estimates. For example, in the 8-puzzle problem, a pattern database for the first three rows of the grid might be combined with the Manhattan distance heuristic for the remaining tiles to produce a more accurate estimate of the remaining cost.