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?


  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.

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


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