Ariel Felner

Pattern Databases (FDBs) are the most common form of memory-based heuristics, and they have been widely used in a variety of permutation puzzles and other domains. We explore the (rue-distance heuristics (TDHs) (also appeared in (Sturtevant et al 2009)) which are a different form of memory-based heuristics, designed to work in problem states where there isn't a fixed goal state. Unlike PDBs, which build a heuristic based on distances in an abstract state space, TDHs store distances which are computed in the actual state space. We look in detail at how TDHs work, providing both theoretical and experimental motivation for their use.