Performance of IDA on Trees and Graphs

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Search and Expert Systems

We present the following results about IDA* and related algorithms: We show that IDA* is not asymptotically optimal in all of the cases where it was thought to be so. In particular, there are trees satisfying all of the conditions previously thought to guarantee asymptotic optimality for IDA*, such that IDA* will expand more than O(N) nodes, where N is the number of nodes eligible for expansion by A*. We present a new set of necessary and sufficient conditions to guarantee that IDA* expands O(N) nodes on trees.