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

Typo in AI:MA Ch3 pg81

Expand Messages
  • Robert Vogler
    The table giving the time and space complexity is wrong for uniform cost search. Instead of b^d it should be b^m for both space and time complexity. This
    Message 1 of 1 , Aug 16, 2001
    • 0 Attachment
          The table giving the time and space complexity is wrong for uniform cost search.  Instead of b^d it should be b^m for both space and time complexity.  This also holds for A* search, so the complexity figures on pg 102 are also in error.
       
          Let me explain.  Let's assume we have a tree where the true solution is 1 layer deep but it requires a cost of 100 to go there.  All other transitions in the tree only cost 1.  (These are all on the non-optimal path).  UCS or A* will expand all of the nodes on the non-optimal paths until depth 100.  The complexity would be b^100 (b^m) for this example.  That is clearly much larger that b^1 (b^d).
       
          I found this while taking a test in my AI class at Brigham Young University.  I had to argue with the teacher to get my points back.
       
      Robert Vogler
       
       
       
    Your message has been successfully submitted and would be delivered to recipients shortly.