Probabilistic analysis of the complexity of A∗

摘要

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.