---
title: "Fast Recursive Formulations for Best-First Search That Allow Controlled Use of Memory"
authors:
  - "Anup K. Sen"
  - "Amitava Bagchi"
doi: ""
url: "https://ijcai.org/proceedings/1989/47"
pdf: "https://ijcai.org/proceedings/1989/0047.pdf"
venue: "Proceedings of the Eleventh International Joint Conference on Artificial Intelligence"
year: 1989
pages: "297-301"
track: "Search"
keywords:
---

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

Anup K. Sen, Amitava Bagchi

*Proceedings of the Eleventh International Joint Conference on Artificial Intelligence*, 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.