On the Asymptotic Performance of IDA*

Abstract

Since best-first search algorithms such as A* require large amounts of memory, they sometimes cannot run to completion, even on problem instances of moderate size. This problem has led to the development of limited-memory search algorithms, of which the best known is IDA*. This paper presents the following results about IDA and related algorithms: The analysis of asymptotic optimality for IDA* in [10] is incorrect. There are trees satisfying the asymptotic optimality conditions given in [10] for which IDA* is not asymptotically optimal. To correct the above problem, we state and prove necessary and sufficient conditions for asymptotic optimality of IDA* on trees. On trees not satisfying our conditions, we show that no best-first limited-memory search algorithm can be asymptotically optimal. On graphs, IDA* can perform quite poorly. In particular, there are graphs on which IDA* does node expansions where N is the number of nodes expanded by A'. (Also cross-referenced as UMIACS-TR-95-22)