May 14, 1999
School of Information Technology and Engineering
University of Ottawa
A Space-Time Tradeoff for Memory-based Heuristics
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. (Korf,1997) conjectures for search using memory-based heuristics that 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.
This is an extended version of a talk that will be given at AAAI'99 in July.