The AIMA tells us that the number of nodes within
the goal contour search space is exponential in the length of solution;
and in "Bibliographical and Historical Notes" It
tells Pohl (1970, 1977) pioneered the study of the relationship between the
error in A*'s heuristic, and the proof that A* runs
in linear time if the error in heuristic function is bounded by a constant can
be found in Pohl (1977) and in Gaschnig
I couln't find Gaschnig (1979), but I found Pohl
(1970, 1977) but I cann't see this proof. In this article the Pohl show
"Total number of nodes expanded" like sums of
| Tj |+ k + 1, but He isn't clear why!!!!
Anyone knows how proof this????
Pohl, I. (1970). First results on the effect of error in heuristic search.
In Meltzer, B. and Michie, D., editors, Machine Intelligence 5, pages
219-236. Elsevier/North-Holland, Amsterdam, London, New York.
Pohl, I. (1977). Practical and theoretical considerations in heuristic
search algorithms. In Elcock, E. W. and Michie, D., editors, Machine
Intelligence 8, pages 55-72. Ellis Horwood, Chichester, England.
Gaschnig, J. (1979). Performance measurement and analysis of certain search
algorithms. Technical Report CMU-CS-79-124, Computer Science Department,