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
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.
Your message has been successfully submitted and would be delivered to recipients shortly.
Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer.
We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.