Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    On the Asymptotic Performance of IDA*

    Thumbnail
    View/Open
    CS-TR-3419.ps (381.3Kb)
    No. of downloads: 243

    Auto-generated copy of CS-TR-3419.ps (316.3Kb)
    No. of downloads: 578

    Date
    1998-10-15
    Author
    Mahanti, Ambuj
    Ghosh, S.
    Nau, Dana S.
    Pal, A. K.
    Kanal, L.N.
    Metadata
    Show full item record
    Abstract
    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)
    URI
    http://hdl.handle.net/1903/701
    Collections
    • Technical Reports from UMIACS
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility