On the Asymptotic Performance of IDA*

Loading...
Thumbnail Image

Files

CS-TR-3419.ps (381.4 KB)
No. of downloads: 243
CS-TR-3419.pdf (316.36 KB)
No. of downloads: 585

Publication or External Link

Date

1998-10-15

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)

Notes

Rights