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
(1979).

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
the

"Total number of nodes expanded" like sums of
| Tj |+ k + 1, but He isn't clear why!!!!

Anyone knows how proof this????

Thanks!!!!

Vilc

P.S.:

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,
Carnegie-Mellon University.