×

Time complexity of iterative-deepening-\(A^{*}\). (English) Zbl 0971.68147

Summary: We analyze the time complexity of iterative-deepening-A\(^{*}\) (IDA\(^{*}).\) We first show how to calculate the exact number of nodes at a given depth of a regular search tree, and the asymptotic brute-force branching factor. We then use this result to analyze IDA\(^{*}\) with a consistent, admissible heuristic function. Previous analyses relied on an abstract analytic model, and characterized the heuristic function in terms of its accuracy, but do not apply to concrete problems. In contrast, our analysis allows us to accurately predict the performance of IDA\(^{*}\) on actual problems such as the sliding-tile puzzles and Rubik’s Cube. The heuristic function is characterized by the distribution of heuristic values over the problem space. Contrary to conventional wisdom, our analysis shows that the asymptotic heuristic branching factor is the same as the brute-force branching factor. Thus, the effect of a heuristic function is to reduce the effective depth of search by a constant, relative to a brute-force search, rather than reducing the effective branching factor.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Culberson, J.; Schaeffer, J., Pattern databases, Comput. Intelligence, 14, 4, 318-334 (1998)
[2] Edelkamp, S.; Korf, R. E., The branching factor of regular search spaces, (Proc. AAAI-98, Madison, WI (1998)), 299-304
[3] Gaschnig, J., Performance measurement and analysis of certain search algorithms, Ph.D. Thesis (1979), Department of Computer Science, Carnegie-Mellon University: Department of Computer Science, Carnegie-Mellon University Pittsburgh, PA
[4] Hart, P. E.; Nilsson, N. J.; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics, 4, 2, 100-107 (1968)
[5] Korf, R. E., Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence, 27, 1, 97-109 (1985) · Zbl 0573.68030
[6] Korf, R. E., Finding optimal solutions to Rubik’s Cube using pattern databases, (Proc. AAAI-97, Providence, RI (1997)), 700-705
[7] Korf, R. E.; Reid, M., Complexity analysis of admissible heuristic search, (Proc. AAAI-98, Madison, WI (1998)), 305-310
[8] Korf, R. E.; Felner, A., Disjoint pattern database heuristics, Artificial Intelligence (Special Issue: Chips Challenging Champions: Advances in Computational Intelligence for Game-Playing) (2001), to appear · Zbl 1050.68034
[9] Pearl, J., Heuristics (1984), Addison-Wesley: Addison-Wesley Reading, MA
[10] Pohl, I., Practical and theoretical considerations in heuristic search algorithms, (Elcock, W.; Michie, D., Machine Intelligence, Vol. 8 (1977), Ellis Horwood: Ellis Horwood Chichester), 55-72
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.