Knowledge versus search: A quantitative analysis using A∗

摘要

This paper analyzes the average 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 distribution may vary over the nodes in the graph. The search model consists of an m-ary tree with unit branch costs and a unique goal state situated at a distance N from the root.The main result states that if the typical error grows like φ(h∗) then the mean complexity of A∗ grows approximately like G(N)exp[cφ(N)], where c is a positive constant and G(N) is O(N2). Thus, a necessary and sufficient condition for maintaining polynomial search complexity is that A∗ be guided by heuristics with logarithmic precision, e.g. φ(N) = (log N)k. A∗ is shown to make much greater use of its heuristic knowledge than a backtracking procedure would under similar conditions.