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

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 as 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 15- puzzle 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.