A Result on the Computational Complexity of Heuristic Estimates for the A Algorithm.
Marco Valtorta · 1983
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)