Tuesday, February 3, 2009

Question on HW1, Problem 7.1

This question asks us to consider the case where solution nodes are distributed non-uniformly throughout a search tree- they can be clustered. It asks whether we should prefer depth-first search or breadth first search.

I guess I'm not sure how clustered solutions matters? I assume b is finite and the search tree has a finite depth. It seems to me that if b is large relative to d, breadth-first would take longer to get "down into the branches" and find a cluster. So we should go with depth-first.

On the other hand, if the tree is deep, but has a small branching factor, breadth-first might be better because we could fairly quickly get down to where clusters might be?

I feel like these are weak, wishy-washy arguments. And neither one has much to do with clustering. I'm not sure how to reason about this. Help?

2 comments:

  1. For this particular problem, there are two assumptions you need to consider
    1) all the solutions are in the depth d
    2) solutions are distributed *NON-UNIFORMLY*.

    Try to decide what assumption(s) might affect your choice of algorithm and how it (they) can affect.

    ReplyDelete
  2. Ah, I didn't fully understand what we meant by a cluster. Thank you!

    ReplyDelete

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