The comparison between the statistical heuristic search and A^*

DOI10.1007/BF02943360MaRDI QIDQ2640290zbMATH OpenFDO

Authors Bo Zhang, Ling Zhang

Publication date 1989

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02943360

zbMATH Keywords

best-first heuristic searchBF searchheuristic statistical search algorithmlocal statisticnode statisticSPRTsubtree evaluation functionsubtree statisticuniform m-ary treeWald sequential probability ratio test

Mathematics Subject Classification ID

Trees (05C05) Sequential statistical analysis (62L10) Sequential statistical methods (62L99) Discrete mathematics in relation to computer science (68R99)

Review text

Assuming G is a uniform m-ary tree, where m is its branching factor, the heuristic statistical search algorithm (SA) consists of the statistical inference method SPRT (Wald sequential probability ratio test) and BF (best-first) heuristic search. Then the procedure of SA search is divided into two steps: First, it quickly identifies the most promising subtree using a subtree evaluation function a(n) (global statistic or subtree statistic). Based on SPRT, from nodes \(n_{11},n_{12},...,n_{1m}\) in the first level, the m search directions, i.e., the subtrees \(T(n_{11}),...,T(n_{1m})\) rooted at nodes \(n_{11},...,n_{1m}\), are selected and rejected, taking the expanded nodes in each subtree as observed samples. The subtrees which contain the goal with lower probability are rejected. The most promising one is selected. Then, it expands nodes within that subtree using a node evaluation function b(n) (local statistic or node statistic).

Recommendations

• scientific article; zbMATH DE number 1308896
• Cost-error relationships in A* tree-searching
• A New Heuristic Search Technique-Algorithm SA
• Why SA can beat the exponential explosion in heuristic search
• Heuristic tree search with nonparametric statistical inference methods

Cites work

• scientific article; zbMATH DE number 3502568 (Why is no real title available?)
• scientific article; zbMATH DE number 3535514 (Why is no real title available?)
• Statistical heuristic search

Cited in

(8)

• Statistical heuristic search
• Concurrent competitive wave approach to hyper-distributed hyper-parallel AI processing
• Are branch and bound and A\(^{\ast}\) algorithms identical?
• Asynchronous heterogeneous mechanism for hyper-distributed hyper-parallel AI processing
• Why SA can beat the exponential explosion in heuristic search
• Heuristic tree search with nonparametric statistical inference methods
• A New Heuristic Search Technique-Algorithm SA
• scientific article; zbMATH DE number 1308896 (Why is no real title available?)

This page was built for publication: The comparison between the statistical heuristic search and \(A^*\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640290)