Institute for Systems Research

Permanent URI for this communityhttp://hdl.handle.net/1903/4375

Browse

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    On the Asymptotic Performance of IDA*
    (1995) Mahanti, Ambuj; Ghosh, Subrata; Nau, D.S.; Pal, A.K.; Kanal, L.N.; ISR
    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* [9, 10]. 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 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 (22N) node expansions where N is the number of nodes expanded by A*.