0
$\begingroup$

I have a question on Search Trees.

I have a balanced, infinite, search tree.

If you check a node at level $l$, the probability of finding a solution at that node is $p^l$.

Questions

The first question is, using breadth-first search, how many solutions will you find on average in an infinitely large tree?

The second question is, using depth-first search, how many solutions will you find on average in an infinitely large tree?

My thinking...

For some reason, I can't get the answer for both out of my head as being 'all of them!' or infinite solutions!

Looking at the way breadth-first search works and taking into account it is a balanced tree, it appears to examine each parent node, and then each of the children of each parent node etc. (Sorry... I know its a crude way to describe - wikipedia does it quite well!) so surely given enough time it will find all of the solutions?

However, for the depth-first, it seems to look at the root node, then the left child, then the left child of that child etc so in an infinite tree surely it won't examine any node except the first one on each level?

Plea

So, hopefully that makes some sense and can someone give me some pointers please?

Thanks

George

$\endgroup$

1 Answer 1

1
$\begingroup$

Hints: Depth-first search will only ever search one infinitely long branch. Breadth-first search will eventually get to each node. Expected value of sum = sum of expected values.

$\endgroup$
3
  • $\begingroup$ Okay thanks :-) I may have interpreted it wrongly, but does that mean this will involve sum to infinity? $\endgroup$
    – delta3506
    Oct 9, 2014 at 14:22
  • $\begingroup$ Thinking more deeply (and preparing to be shot down in flames!) For breadth-first search, if you take the number of nodes on a level ($k^l$) and multiply by the probability of a node on that level is a solution is ($p^l$) can you then do a sum to infinity? $\endgroup$
    – delta3506
    Oct 9, 2014 at 14:53
  • $\begingroup$ Hint: geometric series. $\endgroup$ Oct 12, 2014 at 5:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .