Time Complexity of Iterative-Deepening-A*

Time Complexity of Iterative-Deepening-A*, by Richard E. Korf, Michael Reid and Stefan Edelkamp
Artificial Intelligence 129 (June 2001), no. 1-2, pp. 199-218.
[DOI] [Zentralblatt]
.ps (605k) .ps.gz (111k) .pdf (241k)
We analyze the computational complexity of the search algorithm called "Iterative-Deepening-A*" used in artificial intelligence, under some modest hypotheses. Our theoretical predictions, which are asymptotic, are shown to match the empirically observed behavior of the algorithm, even in relatively small searches.
Research page Home page E-mail
Updated January 8, 2008.