You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).
Improving the Efficiency of Limited-Memory Heuristic Search. Subrata Ghosh. Ambuj Mahanti. Dana S. Nau. February 1995.
This paper describes a new admissible tree search algorithm called Iterative Threshold Search (ITS). ITS can be viewed as a much-simplified version of MA*, and a generalized version of MREC ITS's node selection and retraction (pruning) overhead is much less expensive than MA*'s. We also present the following results: 1. Every node generated by ITS is also generated by IDA*, even if ITS is given no more memory than IDA*. In addition, there are trees on which ITS generates 0(N) nodes in comparison to 0(N log N) nodes generated by IDA*, where N is the number of nodes eligible for generation by A*. 2. Experimental tests show that if the heuristic branching factor is low and the nodegeneration time is high (as in most practical problems), then ITS can provide significant savings in both number of node generations and running time. 3. Our experimental results also suggest that on the Traveling Salesman Problem, both IDA* and ITS are asymptotically optimal on the average if the costs between the cities are drawn from a fixed range. However, if the rake of costs grows in proportion to the problem size, then IDA* is not asymptotically optimal. ITS's asymptotic complexity in the latter case depends on the amount of memory available to it. (Also cross-referenced as UMIACS-TR-95-23) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Ambuj Mahanti. S. Ghosh. Dana S. Nau. A. K. Pal. L.N. Kanal. On the Asymptotic Performance of IDA*. February 1995.
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*. 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 conditions 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 node expansions where N is the number of nodes expanded by A'. (Also cross-referenced as UMIACS-TR-95-22) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Last Generated Fri Aug 11 04:01:01 EDT 2000