Performance of IDA on Trees and Graphs

A. Mahanti, S. Ghosh, D. S. Nau, L. N. Kanal, A. K. Pal

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.