• C

# logic question

i have no idea where i should ask this question but here is as good as anywhere i guess...

If someone writes down a random number (natural number) what s the best strategy for searching a tree of the following type in order to guess the number:

empty
/   |   |  \ .....etc
0    1   3   4 .....etc
/ | \    /\   /\  /\ ....etc
00 01 02.........etc

if that makes any sense?
basically its to do with depthfirst/breadthfirst strategies
and id like to know the best strategy for this search without going into an infinite loop...

thanks
paul
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Some questions:

Are those numbers or strings ? (00, 01, ...)

Are the numbers in some order in the tree ?

Is the tree finite ?

BTW, is it a tree or a graph ?

In general, you can search any finite tree/graph with either depth-first or breadth-first strategy, without any problem. Breadth-first consumes much more memory, and is usually harder to implement (so depth-first would be the method of choice, unless we know something else :).

For an infinite tree/graph depth first is NOT guaranteed to find the answer, I think, while breadth-first is.

Also, if you have more info about the tree and/or nodes, some other algorithms may be better (A*, branch & bound etc), and if the nodes are ordered, then of course you can do much better :)

Orlando
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
binary search, like the number guessing game. For a number n between L and N, make the first guess at (L+N)/2. if x is smaller, the range becomes L .. N/2 (guess at (L+N)/4). If x is larger, the search range becomes (L+N)/2 +1 .. N (guess at ((L+N)/2 + 1 + N)/2). etc...
0
Commented:
qn: y is 00 different from 0? then it's not just a no?
anyway, since there are infinite natural numbers, BFS is the way to go...
easy implementation (if 00 and 000 are different from 0 say) is
go thru all single digit nos, ie. [0, 9]
then double [00, 99]
then triple blahblah

if 00 is same as 0 then just go from 0 onwards...

of course that is if u can only get the answer to "is __ the number?"

otherwise binary would be best if u can get the answer to "is __ bigger/less than the number?"
0
Commented:
I think ur question is similar to
searching words in Dictionary.
I would also like to know the answer.
0
Commented:
Are you guessing digit-by-digit or the while number (i.e., 123 as "0?", "No.", "1?", "Yes; first digit correct."; "0?", "No.", etc.), or "0?", "No 0.", "1?", "Yes, there's (one or more) 1."?
0
Commented:
How do you decide on your branches?
What information do you recieve when you guess?
0
Commented: