Robert C. Holte and István T. Hernádvölgyi, University of Ottawa
A memory-based heuristic is a function, h(s), stored in the form of a lookup table (pattern database): h(s) is computed by mapping s to an index and then retrieving the appropriate entry in the table. (Korf97) conjectures that for A* search using memory-based heuristics m*t is a constant, where m is the size of the heuristic’s lookup table and t is search time. In this paper we present a method for automatically generating memory-based heuristics and use this to test Korf’s conjecture in a large-scale experiment. The results strongly support Korf’s conjecture.