Performance of IDA on Trees and Graphs

Abstract

We present the following results about IDA* and related algorithms: ffl 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*. ffl We present a new set of necessary and sufficient conditions to guarantee that IDA* expands O(N ) nodes on trees. ffl On trees not satisfying the above conditions, there is no best-first admissible tree search algorithm that runs in S = N=/(N ) (where /(N ) 6= O(1)) memory and always expands O(N ) nodes. ffl There are acyclic graphs on which IDA* expands \\Omega\\Gamman 2N ) nodes. Introduction Heuristic search is applicable to a wide range of combinatorial optimization problems. The objective of many heuristic search algorithms is to find a minimum cost solution path in ...