A Space-Time Tradeoff for Memory-Based Heuristics

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.