In this paper we present a heuristic search algorithm, DBIDA*, which uses a given, bounded memory of size m. Previously published algorithms like IDA*, IDA*-CR, MA*, SMA*, etc. expand up to Ω(n 2) nodes, where n is the number of nodes expanded by A*, or suffers from an high overhead per node expansion which limits their applicability to practical problems.
We show that our algorithm expands at most O(dn 2/m) nodes where d is the length of the computed path from the start node to a destination node and m the number of storable nodes. If a sufficiently large memory is used, the number of node expansions can, thus, be significantly reduced. Furthermore, only a few update operations are necessary in the data structures used which leads to an additional reduction of the running time. Experimental results show that in contrast to former approaches our algorithm works well compared with IDA* in the domain of the 15-puzzle. The number of node expansions can be reduced significantily by using only a small number of additional data structure operations.