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* [9, 10]. 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.<P>To correct the above problem, we state and prove necessary and sufficient 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.<P>On graphs, IDA* can perform quite poorly. In particular, there are graphs on which IDA* does (22N) node expansions where N is the number of nodes expanded by A*.