This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browsing Institute for Systems Research Technical Reports by Subject "A* IDA* algorithms combinatorics"
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  is incorrect. There are trees satisfying the asymptotic optimality conditions given in  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*.