Title :
NSA algorithm and its computational complexity-preliminary results
Author_Institution :
Dept. of Comput. Sci., Old Dominion Univ., Norfolk, VA, USA
Abstract :
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 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)2), where N is the length of the solution path
Keywords :
computational complexity; heuristic programming; inference mechanisms; search problems; statistics; trees (mathematics); computational complexity; goal; nonparametric statistical algorithm; probability; search tree; solution path length; statistical heuristic searching; statistical inference methods; Algorithm design and analysis; Artificial intelligence; Computational complexity; Computer science; Cost function; Heuristic algorithms; Inference algorithms; Parametric statistics; Probability; Random variables;
Conference_Titel :
Tools for Artificial Intelligence, 1989. Architectures, Languages and Algorithms, IEEE International Workshop on
Conference_Location :
Fairfax, VA
Print_ISBN :
0-8186-1984-8
DOI :
10.1109/TAI.1989.65352