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

771Chapter 04, Complexity of A*

Expand Messages
  • Vilc Queupe Rufino
    Aug 30 6:20 PM
    • 0 Attachment
      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.