771Chapter 04, Complexity of A*
- Aug 30, 2007The 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 theerror in A*'s heuristic, and the proof that A* runs in linear time if the error in heuristic function is bounded by a constant canbe 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!!!!VilcP.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.