---
title: "The Statistical Inference Method in Heuristic Search Techniques"
authors:
  - "Ling Zhang"
  - "Bo Zhang"
doi: ""
url: "https://ijcai.org/proceedings/1983/182"
pdf: "https://ijcai.org/proceedings/1983/0182.pdf"
venue: "Proceedings of the Eighth International Joint Conference on Artificial Intelligence"
year: 1983
pages: "757-758"
track: "Planning and Search"
keywords:
---

# The Statistical Inference Method in Heuristic Search Techniques

Ling Zhang, Bo Zhang

*Proceedings of the Eighth International Joint Conference on Artificial Intelligence*, pages 757-758.

## Abstract

In this paper we present a new heuristic searching algorithm by introducing statistical inference method on the basis of algorithm A*, It's called al g orithm SA*, The followin g results have been proved. (1) Al gorithm SA* is super .Lor to al g orith m A*. ( 2 ) The mean complexity of SA* is CN 2 , but in some case A* exhibits exponential complexity (e N) , (J) In a (N ,d,F ) -ga me tree , the mean complexity o f S A* is CN 1 , b ut t~e complexity of other known gamesearching algori thm (-~, SSS* etc.) is at least d>l. (4)The maximal storage-space required by SA* is c,N. Thishows that under a given significance l evel S A* is superior to other known algorithm (e . g , A*, B* , ct..fJ , SS S* etc, ) ,