A Result on the Computational Complexity of Heuristic Estimates for the A Algorithm.

Abstract

The performance of a new heuristic search algorithm is analyzed. The algorithm uses a formal representation that contains enough information to compute the heuristic evaluation function h(n), without requiring a human expert to provide it. The new algorithm is shown to be less efficient than the Dijkstra algorithm, according to the complexity measure number of node expansion. Researchers attempt an interpretation of this strong negative result. Other properties of the new algorithm are discussed in references Valt80, GSoma79, GSValt80. A short discussion of related research, some of which is in progress, concludes the paper. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1983
Accession Number
ADA127901

Entities

People

  • Marco Valtorta

Organizations

  • Duke University

Tags

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Literature
  • Scientific Research
  • Security
  • Sequences
  • Skeleton
  • Universities

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Linear Algebra
  • Systems Analysis and Design