NSA ALGORITHM AND ITS COMPUTATIONAL COMPLEXITY
Weixiong Zhang · 1989
Introducing statistical inference methods into heuristic search may greatly improve the efficiency of heuristic search and decrease the computational complexity. Until now, however, only the utilization of parametric statistical inference methods are concerned. The effectiveness of the statistical heuristic search will depend on the assumption to the distibution of the statistic U (n), which characterizes the subtree T(n) rooted at node n. As the consequence, the model of statistical heuristic search is largely limited, and its application is unexpectedly constrained. To beat this shortcoming, the paper proposes the idea of combining nonparametric statistical inference methods with the heuristic search. A nonparametric statistical heuristic search, algorithm NSA, 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, locating at a unknown site in the N-th depth, NSA may find the goal asymptotically with probability one, and the complexity remains 0 (N(/~LN)~), where N is the length of the solution path.