Time complexity of iterative-deepening-A*

被引:69
作者
Korf, RE [1 ]
Reid, M
Edelkamp, S
机构
[1] Univ Calif Los Angeles, Dept Comp Sci, Los Angeles, CA 90095 USA
[2] Univ Massachusetts, Dept Math & Stat, Amherst, MA 01003 USA
[3] Inst Informat, D-79110 Freiburg, Germany
基金
美国国家科学基金会;
关键词
problem solving; heuristic search; iterative-deepening-A*; time complexity; branching factor; heuristic branching factor; sliding-tile puzzles; eight puzzle; fifteen puzzle; Rubik's cube;
D O I
10.1016/S0004-3702(01)00094-7
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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-ford 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. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:199 / 218
页数:20
相关论文
共 8 条
[1]   Pattern databases [J].
Culberson, JC ;
Schaeffer, J .
COMPUTATIONAL INTELLIGENCE, 1998, 14 (03) :318-334
[2]  
Edelkamp S, 1998, FIFTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-98) AND TENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICAL INTELLIGENCE (IAAI-98) - PROCEEDINGS, P299
[3]  
GASCHNIG J, 1979, THESIS CARNEGIEMELLO
[4]   A FORMAL BASIS FOR HEURISTIC DETERMINATION OF MINIMUM COST PATHS [J].
HART, PE ;
NILSSON, NJ ;
RAPHAEL, B .
IEEE TRANSACTIONS ON SYSTEMS SCIENCE AND CYBERNETICS, 1968, SSC4 (02) :100-+
[5]  
KORF R, 2001, IN PRESS ARTIFICIAL
[6]  
Korf R. E., 1997, P 14 NAT C ART INT, P700
[7]   DEPTH-1ST ITERATIVE-DEEPENING - AN OPTIMAL ADMISSIBLE TREE-SEARCH [J].
KORF, RE .
ARTIFICIAL INTELLIGENCE, 1985, 27 (01) :97-109
[8]  
Pohl I, 1977, MACH INTELL, V8, P55