A New Heuristic Search Technique-Algorithm SA

B Zhang; L Zhang

doi:10.1109/tpami.1985.4767624

A New Heuristic Search Technique-Algorithm SA

IEEE Trans Pattern Anal Mach Intell. 1985 Jan;7(1):103-7. doi: 10.1109/tpami.1985.4767624.

Authors

B Zhang¹, L Zhang

Affiliation

¹ Department of Computer Engineering and Science, Tsinghua University, Beijing, People's Republic of China.

PMID: 21869246
DOI: 10.1109/tpami.1985.4767624

Abstract

In this paper, we present a new heuristic searching algorithm by introducing the statistical inference method on the basis of algorithm A (or A*). It is called algorithm SA. In a simplified search space, a uniform m-ary tree, we obtain the following result. Using algorithm SA, a goal node can be found with probability one, and its mean complexity is O(N·ln N) where N is the depth at which the goal is located.