Cost-error relationships in A* tree-searching

ABSTRACT

Pearl has shown that, in admissible A* tree-searching, the expected number of nodes expanded is bounded above and below by exponential functions of heuristic error. An additional assumption required for the validity of Pearl's argument is given. The assumption's significance and interpretation are discussed.

REFERENCES

• 1: Gillea Brassard, Crusade for a better notation, ACM SIGACT News, v.17 n.1, p.60-64, June 1985 [doi>10.1145/382250.382808]
• 2: Gilles Brassard , Paul Bratley, Algorithmics: theory & practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 3: DAVIS, H.W. Some effects of heuristic errors in admissible A* tree-searching. Tech. Rep. WSU- CS-89-01, Department of Computer Science and Engineering, Wright State Univ., Dayton, Ohio, 1989.
• 4: PEARL, J. Heuristics. Addison-Wesley, Reading, Mass., 1984.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Theory