Premium
Pattern Databases
Author(s) -
Culberson Joseph C.,
Schaeffer Jonathan
Publication year - 1998
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/0824-7935.00065
Subject(s) - database , upper and lower bounds , set (abstract data type) , computer science , tile , space (punctuation) , data mining , algorithm , mathematics , programming language , art , mathematical analysis , visual arts , operating system
The efficiency of A* searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject to constraints on the subgoal size. Each subgoal in the database provides a tight lower bound on the cost of achieving it. For a given state in the search space, all possible subgoals are looked up in the pattern database, with the maximum cost over all lookups being the lower bound. For sliding tile puzzles, the database enumerates all possible patterns containing N tiles and, for each one, contains a lower bound on the distance to correctly move all N tiles into their correct final location. For the 15‐Puzzle, iterative‐deepening A* with pattern databases(N ="8) reduces the total number of nodes searched on a standard problem set of 100 positions by over 1000‐fold.