A Result on the Computational Complexity of Heuristic Estimates for the A Algorithm.
DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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
- Theoretical Mathematics