On the Asymptotic Performance of IDA*
On the Asymptotic Performance of IDA*
Files
Publication or External Link
Date
1998-10-15
Authors
Mahanti, Ambuj
Ghosh, S.
Nau, Dana S.
Pal, A. K.
Kanal, L.N.
Advisor
Citation
DRUM DOI
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)