Technical Report No. 150 - Abstract

Stefan Edelkamp
Prediction of Regular Search Tree Growth by Spectral Analysis

The analysis of the time complexity of the IDA* algorithm has shown that predicting the growth of the search tree essentially relies on only two criteria: The number of nodes in the brute-force search tree and the equilibrium distribution of heuristic estimate. Since the latter can be approximated by random sampling we accurately predict the number of nodes of the brute-force search tree for large depth by analyzing the spectrum of the problem graph or one of its factorization. We further derive that the asymptotic brute-force branching factor is in fact the spectral radius of the problem graph and exemplify our considerations in the domain of the (n^2-1)-Puzzle.