Is there an algorithm for finding an item that matches certain properties, like a 20 questions game?

Question

However, if I'm understanding it correctly, the answers seem to assume that each question will go down a hierarchical branching tree. A binary tree should work if the game went like this:

1. Is it an animal? Yes.

2. Is it a mammal? Yes.

3. Is it a feline? Yes.

Because feline is an example of a mammal and mammal is an example of an animal. But what if the questions go like this?

1. Is it a mammal? Yes.

2. Is it a predator? Yes.

3. Does it have a long nose? No.

You can't branch down a tree with those kinds of questions, because there are plenty of predators that aren't mammals. So you can't have your program just narrow it down to mammal and have predators be a subset of mammals.

So is there a way to use a binary search tree that I'm not understanding or is there a different algorithm for this problem?

Just to clarify, I'm only using 20 questions as an example, so my question is about this kind of search problem in general, not other problems involved specifically in a 20 questions game.

Answer 1

It is even more tricky when you have to take the fact that people answer consistently incorrectly into account if for instance a lot of people think that dolphins are fish... That is why you need some more interconnected approach, like ANN or other machine learning.

It's compared to a binary search in that each question is yes/no, and so every answer partitions your remaining set into two parts. But, the data set would likely not be stored in an actual binary tree, because as you realize, that'd only work if the questions were asked in the same order as the tree split dimension.

Also, you can simply have more than exactly 20 dimensions or the properties on which to split things, and some set of those twenty could be shared by more than one object so that the leaf node of a 20-level binary tree wouldn't necessarily contain just one item.

Therefore, the "binary search" is only a metaphor for what's going on, in that at each step you try to pick the property which best splits your remaining set into two halves. As far as actual data structures proceed, you'd have to use something else.

If you wish to know more about Neural Network visit this Neural Network Tutorial.