Monday, February 2, 2009

Space complexity of width-first search

Hi All,

I am confused about the space complexity of the width-first search, which is discussed in the first paragraph of page 74 in the textbook as

"Every node that is generated must remain in memory, because it is either part of the fringe or is an ancestor of a fringe node. The space complexity is, therefore, the same as the time complexity (plus one node for the root)."

To me, the ancestors of fringe nodes are already expanded and thus do not need to be in memory.

Shuiwang

3 comments:

  1. I don't have the book in front of me, but think of depth first search as a comparison. When you get start at the root and go all the way to a leaf, if there was no solution you can toss out all nodes that you checked all children of- they no longer need to stay in memory.

    But in breadth-first you won't be able to toss out any nodes until you're on the deepest row, and have checked almost the whole tree.

    And the reason you can't throw out nodes is because when you do find a goal node, you have to be able to follow its ancestors all the way back to the root. Right?

    ReplyDelete
  2. I agree with Cameron, you need all the nodes in memory to be able to return the path of nodes from the initial to goal node.

    ReplyDelete
  3. Doug and Cameron are basically right.

    rao

    ReplyDelete

Note: Only a member of this blog may post a comment.