Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

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.

Browse

Author: search.filters.author.Mahanti, AmbujSubject: search.filters.subject.computational complexity

Search Results

Now showing 1 - 2 of 2
  • 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*.

  • Thumbnail Image
    Item
    Improving the Efficiency of Limited-Memory Heuristic Search
    (1995) Ghosh, Subrata; Mahanti, Ambuj; Nau, D.S.; ISR
    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*[2], and a generalized version of MREC [15]. 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 O(N) nodes in comparison to O(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 node- generation 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 range of costs grows in proportion to the problem size, then IDA* is not asymptotically optimal. ITS's asymptotic complexity in the later case depends on the amount of memory available to it.