Space-Efficient Memory-Based Heuristics

Abstract

A memory-based heuristic is a heuristic function that is stored in a lookup table. Very accurate heuristics have been created by building very large lookup tables, sometimes called pat-tern databases. Most previous work assumes that a memory-based heuristic is computed for the entire state space, and the cost of computing it is amortized over many problem in-stances. But in some cases, it may be useful to compute a memory-based heuristic for a single problem instance. If the start and goal states of the problem instance are used to re-strict the region of the state space for which the heuristic is needed, the time and space used to compute the heuristic may be substantially reduced. In this paper, we review recent work that uses this idea to compute space-efficient heuristics for the multiple sequence alignment problem. We then describe a novel development of this idea that is simpler and more gen-eral. Our approach leads to improved performance in solv-ing the multiple sequence alignment problem, and is general enough to apply to other domains.