Accession Number:

ADA127901

Title:

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

Descriptive Note:

Technical rept.,

Corporate Author:

DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1983-01-01

Pagination or Media Count:

27.0

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 hn, 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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE