Pattern Databases Store optimal solutions to subproblems in database –We use an exhaustive search to solve every permutation of the 1,2,3,4-piece subproblem of the 8-puzzle –During solution of 8-puzzle, look up optimal cost to solve the 1,2,3,4-piece sub-problem and use as heuristic –Other configurations can be considered
{"Image DocumentName": "Inventing admissible heuristics: Sub-problem solutions as heuristic", "Image ImageDescription": "What is the optimal cost of solving some portion of original problem? subproblem solution is heuristic of original problem.", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}