Heuristic Search

Chapter 6. Memory-Restricted Search

This chapter studies different algorithms that explore the middle ground between linear-space algorithms like IDA* and memory-sensitive algorithms like A*. It considers transposition tables for full and lossy/lossless sparse state set representations, as well as omission schemes for frontier and visited state sets.

Keywords: transposition table, fringe search, iterative threshold search, SMAG, enforced hill-climbing, weighted A, overconsistent A*, anytime repairing A*, k-best-first search, beam search, partial A*, partial IDA*, frontier search, sparse-memory graph search, breadth-first heuristic search, locality, beam-stack search, partial expansion A*, two-bit breadth-first search

In the previous chapter, ...