Stochastic node caching for memory-bounded search

Teruhisa Miura*, Toru Ishida

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

14 Citations (Scopus)


Linear-space search algorithms such as IDA* (Iterative Deepening A*) cache only those nodes on the current search path, but may revisit the same node again and again. This causes IDA* to take an impractically long time to find a solution. In this paper, we propose a simple and effective algorithm called Stochastic Node Caching (SNC) for reducing the number of revisits. SNC caches a node with the best estimate, which is currently known of the minimum estimated cost from the node to the goal node. Unlike previous related research such as MREC, SNC caches nodes selectively, based on a fixed probability. We demonstrate that SNC can effectively reduce the number of revisits compared to MREC, especially when the state-space forms a lattice.

Original languageEnglish
Number of pages7
Publication statusPublished - 1998 Jan 1
Externally publishedYes
EventProceedings of the 1998 15th National Conference on Artificial Intelligence, AAAI - Madison, WI, USA
Duration: 1998 Jul 261998 Jul 30


OtherProceedings of the 1998 15th National Conference on Artificial Intelligence, AAAI
CityMadison, WI, USA

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


Dive into the research topics of 'Stochastic node caching for memory-bounded search'. Together they form a unique fingerprint.

Cite this