Presentation | 1997/1/22 Stochastic Node Caching for memory bounded search Teruhisa Miura, Toru Ishida, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Linear space search algorithms only keep nodes on the current search path. But they may revisit the same node repeatedly, and thus it may take unpractically long time to find a solution. In this paper, we propose a simple and effective algorithm called Stochastic Node Caching for reducing revisits. It keeps a node in memory with some fixed probability when the node is expanded. To demonstrate the effectiveness of Stochastic Node Caching, we compared it with MREC. We applied them to the 15 puzzle and the multiple sequence alignment. On the multiple sequence alignment, the achievement was about 70% reduction in the total number of visits compared to MREC. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | linear-space search / memory-bounded search / 15 Puzzle / IDA^* / MREC |
Paper # | AI96-35 |
Date of Issue |
Conference Information | |
Committee | AI |
---|---|
Conference Date | 1997/1/22(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Artificial Intelligence and Knowledge-Based Processing (AI) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Stochastic Node Caching for memory bounded search |
Sub Title (in English) | |
Keyword(1) | linear-space search |
Keyword(2) | memory-bounded search |
Keyword(3) | 15 Puzzle |
Keyword(4) | IDA^* |
Keyword(5) | MREC |
1st Author's Name | Teruhisa Miura |
1st Author's Affiliation | Department of Information Science, Kyoto University() |
2nd Author's Name | Toru Ishida |
2nd Author's Affiliation | Department of Information Science, Kyoto University |
Date | 1997/1/22 |
Paper # | AI96-35 |
Volume (vol) | vol.96 |
Number (no) | 453 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |