On the Asymptotic Performance of IDA*
| dc.contributor.author | Mahanti, Ambuj | en_US |
| dc.contributor.author | Ghosh, S. | en_US |
| dc.contributor.author | Nau, Dana S. | en_US |
| dc.contributor.author | Pal, A. K. | en_US |
| dc.contributor.author | Kanal, L.N. | en_US |
| dc.date.accessioned | 2004-05-31T22:30:30Z | |
| dc.date.available | 2004-05-31T22:30:30Z | |
| dc.date.created | 1995-02 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.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) | en_US |
| dc.format.extent | 390552 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/701 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3419 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-95-22 | en_US |
| dc.title | On the Asymptotic Performance of IDA* | en_US |
| dc.type | Technical Report | en_US |