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?
Subscribe to:
Post Comments (Atom)
For this particular problem, there are two assumptions you need to consider
ReplyDelete1) 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.
Ah, I didn't fully understand what we meant by a cluster. Thank you!
ReplyDelete