Information Systems Engineering

Pattern Databases (PDBs) 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 true-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 theoret-ical and experimental motivation for their use