NSA algorithm and its computational complexity-preliminary results
Weixiong Zhang · 2003
To overcome the limitations of models of statistical heuristic searching the author proposes the idea of combining nonparametric statistical inference methods with the heuristic search. A nonparametric statistical algorithm (NSA) for heuristic searching is presented, and its computational complexity is discussed. It is shown that, in a uniform m-ary search tree G with a single goal S/sub N/ located at an unknown site in the N-th depth, NSA can find the goal asymptotically with probability one, and the complexity remains O(N(In N)/sup 2/), where N is the length of the solution path.>