𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Probabilistic analysis of the complexity of A∗

✍ Scribed by Nam Huyn; Rina Dechter; Judea Pearl

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
598 KB
Volume
15
Category
Article
ISSN
0004-3702

No coin nor oath required. For personal study only.

✦ Synopsis

This paper analyzes the number of nodes expanded by A* as a function of the accuracy of its heuristic estimates by treating the errors h * -h as random variables whose distributions may vary over the nodes in the graph. Our model consists of an m -ary tree with unit branch costs and a unique goal state situated at a distance N from the root.

Two results are established:

(

1) for any error distribution, if A '[ is stochastically more informed than A ~, then A T is stochastically more efficient than A ~., and

(2) if the probability that the relative error be bounded away from zero is greater than l/m, then the average complexity of A * is exponential with N, whereas if the probability of zero error is greater than 1 -l/m, the average complexity is O(N).

📜 SIMILAR VOLUMES

Complexity analysis of the SAT engine: D
Complexity analysis of the SAT engine: DNA algorithms as probabilistic algorithms
✍ Masami Hagiya; John A. Rose; Ken Komiya; Kensaku Sakamoto 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 123 KB

Taking advantage of the power of DNA molecules to spontaneously form hairpin structures, Sakamoto et al. designed a molecular algorithm to solve instances of the satisÿability problem on Boolean expressions in clausal form (the SAT problem), and by developing new experimental techniques for molecula

Probabilistic analysis of the time compl
Probabilistic analysis of the time complexity of quicksort
✍ Tadashi Mizoi; Shunji Osaki 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 460 KB

## Abstract Quicksort is a well‐known sorting algorithm based on the divided control. the array to be sorted is divided into two sets as follows. an element in the array is specified, and the set of values larger than the value of that element and the set of values smaller than that value are const

A low complexity approximation of probab
A low complexity approximation of probabilistic appearance models
✍ Raouf Hamdan; Fabrice Heitz; Laurent Thoraval 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 633 KB

on Computer Vision, Cambridge, MA, June 1995, p. 687; IEEE Trans. Pattern Anal. Mach. Intell. 19 (7) (1997) 696) has recently shown excellent performances in pattern detection and recognition, outperforming most other linear and non-linear approaches. Unfortunately, the complexity of this model rema

Probabilistic setting of information-bas
Probabilistic setting of information-based complexity
✍ H Woźniakowski 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 746 KB

We study the probabilistic (E, b)-complexity for linear problems equipped with Gaussian measures. The probabilistic (E, S)-complexity, comp@'(e, 6), is understood as the minimal cost required to compute approximations with error at most e on a set of measure at least 1 -6. We find estimates of comp@

A probabilistic upper bound for the edge
A probabilistic upper bound for the edge identification complexity of graphs
✍ Eberhard Triesch 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 344 KB

Given a finite graph G=( V, E), what is the minimum number c(G) of incidence tests which are needed in the worst case to identify an unknown edge e\*EE? The number c(G) was first studied by Aigner and Triesch (1988), where it was shown that for almost all graphs in the random graph model where d(n)