Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0971.68147
Korf, R.E.; Reid, M.; Edelkamp, S.
Time complexity of iterative-deepening-$A^{*}$. (English)
[J] Artif. Intell. 129, No.1-2, 199-218 (2001). ISSN 0004-3702

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 2000:: *68T20 Problem solving
68Q25 Analysis of algorithms and problem complexity

Keywords: problem solving; heuristic search; iterative-deepening-A; time complexity; branching factor; heuristic branching factor; sliding-tile puzzles; eight puzzle; fifteen puzzle; Rubik's Cube

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Simple Search

Zentralblatt MATH Berlin [Germany]