Analysis of iterative-deepening-A~*
Bai Zhi-jiang, Wei Han · Journal of Shanghai, Maritime University · 2005
The running time of iterative-deepening-A~*(IDA~*) algorithm is analyzed with heuristic function of the problem space and the effect of the function is to reduce the actual search depth. Moreover, the analysis has indicated that the asymptotic heuristic branching factor is same as the brute-force branching factor. The experimental result shows that the performance of IDA~* on actual problems such as Puzzles can be accurately predicted with the main conclusion.