Usage
  • 9 views
  • 21 downloads

Effective Bidirectional A* with Frontier Search and External-Memory Utilization

  • Author(s) / Creator(s)
  • Technical report TR08-18. We present an advanced Bidirectional A* algorithm featuring an application of Frontier Search and a strategy for the performance-efficient utilization of External Memory. We present the results of an experimental evaluation demonstrating that this algorithm is capable of tackling exceptionally large state spaces while consuming significantly less time and space than its A* counterpart. For instance, in solving difficult instances of the 5-by-5 Sliding-Tile Puzzle and the 4-peg Towers-of-Hanoi problems, using additive pattern-database heuristics, the typical reductions in time- and space-consumption are in the range of one to two orders of magnitude. | TRID-ID TR08-18

  • Date created
    2008
  • Subjects / Keywords
  • Type of Item
    Report
  • DOI
    https://doi.org/10.7939/R3J09WB0G
  • License
    Attribution 3.0 International