Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem. Academic Article uri icon


  • Abstract We integrate a number of recent advances in heuristic search, and apply them to the four-peg Towers of Hanoi problem. These include frontier search, disk-based search, multiple compressed disjoint additive pattern database heuristics, and breadth-first heuristic search. The main new idea we introduce here is the use of pattern database heuristics to search for any of a number of explicit goal states, with no overhead compared to a heuristic for a single goal state. We perform the first complete breadth-first searches of the 21 and …

publication date

  • January 1, 2007

published in