Time complexity of iterative-deepening-A [formula omitted]

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 fu...

Full description

Saved in:
Bibliographic Details
Published in:Artificial intelligence 2001-06, Vol.129 (1), p.199-218
Main Authors: Korf, Richard E., Reid, Michael, Edelkamp, Stefan
Format: Article
Language:English
Subjects:
Artificial intelligence
Branching factor
Eight Puzzle
Fifteen Puzzle
Heuristic branching factor
Heuristic methods
Heuristic search
Iterative-deepening-A [formula omitted]
Problem solving
Rubik's Cube
Searching
Sliding-tile puzzles
Time complexity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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.
ISSN:0004-3702
1872-7921
DOI:10.1016/S0004-3702(01)00094-7