Loading ...
Sorry, an error occurred while loading the content.

771Chapter 04, Complexity of A*

Expand Messages
  • Vilc Queupe Rufino
    Aug 30, 2007
      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????
      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.