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) : Valtorta,Marco


Full Text : http://www.dtic.mil/get-tr-doc/pdf?AD=ADA127901


Report Date : Jan 1983


Pagination or Media Count : 27


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)


Descriptors :   *ALGORITHMS , *ESTIMATES , *INFORMATION RETRIEVAL , *HEURISTIC METHODS , TEST AND EVALUATION , PERFORMANCE(ENGINEERING) , SEARCHING


Subject Categories : Theoretical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE