Proceedings

Fast Recursive Formulations for Best-First Search That Allow Controlled Use of Memory

Anup K. Sen, Amitava Bagchi

Download BibTeX Cite

Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Search. Pages 297-301.

Abstract

MREC is a new recursive best-first search algorithm which combines the good features of A* and IDA*. It is closer in operation to IDA*, and does not use an OPEN list. In order to execute, all MREC needs is sufficient memory for its implicit stack. But it can also be fed at runtime a parameter M which tells it how much additional memory is available for use. In this extra memory, MREC stores as much a<; possible of the explicit graph. When M = 0, MREC is identical to IDA*. But when M > 0, it can make far fewer node expansions than IDA*. This can be advantageous for problems where the time to expand a node is significant. Extensive runs on a variety of search problems, involving search graphs that may or may not be trees, indicate that MREC with M = 0 is as good as IDA* on problems such as the 15puzzle for which IDA* is suitable, while MREC with large M is as fast as A* on problems for which node expansion time is not negligible.

Anup K. Sen, and Amitava Bagchi. 1989. Fast Recursive Formulations for Best-First Search That Allow Controlled Use of Memory. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89. IJCAI, 297–301. https://ijcai.org/proceedings/1989/47
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards