Show simple item record

dc.contributor.authorMahanti, Ambujen_US
dc.contributor.authorGhosh, Subrataen_US
dc.contributor.authorNau, D.S.en_US
dc.contributor.authorPal, A.K.en_US
dc.contributor.authorKanal, L.N.en_US
dc.date.accessioned2007-05-23T09:58:52Z
dc.date.available2007-05-23T09:58:52Z
dc.date.issued1995en_US
dc.identifier.urihttp://hdl.handle.net/1903/5624
dc.description.abstractSince 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.<P>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.<P>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*.en_US
dc.format.extent1316991 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1995-36en_US
dc.subjectsearchen_US
dc.subjectasymptotic optimalityen_US
dc.subjectA* IDA* algorithms combinatoricsen_US
dc.subjectcomputational complexityen_US
dc.subjectSystems Integration Methodologyen_US
dc.titleOn the Asymptotic Performance of IDA*en_US
dc.typeTechnical Reporten_US
dc.contributor.departmentISRen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record