是否有一种算法可以找到与某些属性相匹配的项，比如一个20个问题游戏？

Question

一个关于20个问题游戏的问题被问到这里

然而，如果我正确地理解了它，答案似乎假设每个问题都会沿着分层分支树向下。如果游戏是这样的，那么二叉树应该可以工作：

1. 是动物吗？是。
2. 是哺乳动物吗？是。
3. 是猫科动物吗？是。

因为猫是哺乳动物的例子，哺乳动物是动物的例子。但如果问题是这样的呢？

1. 是哺乳动物吗？是。
2. 它是食肉动物吗？是。
3. 它有长鼻子吗？不是的。

你不能用这些问题把树砍下来，因为有很多不是哺乳动物的捕食者。所以你不能把程序缩小到哺乳动物身上，让捕食者成为哺乳动物的一个子集。

那么，是否有一种方法可以使用我不理解的二叉树，还是有不同的算法来解决这个问题呢？

为了澄清，我只是用20个问题作为例子，所以我的问题是关于这类搜索问题，而不是在一个20个问题游戏中专门涉及的其他问题。

Answer 1

它被比作二进制搜索，因为每个问题都是“是”/“否”，所以每个答案都将剩余的集合划分为两个部分。但是，数据集可能不会存储在实际的二叉树中，因为正如您所认识到的，只有当问题总是按照树拆分维度的相同顺序询问时，这才能工作。

而且，您可以很容易地拥有超过20个维度(“属性”)来分割事物，而其中的一些集合可以由多个对象共享(这样，20层二叉树的叶节点就不一定只包含一个项)。

因此，“二进制搜索”仅仅是对实际发生的事情的隐喻，在每一步中，你都试图选择一个属性，它最好地将你剩下的集合分割成两个相等的一半。就实际的数据结构而言，您必须使用其他的东西。

Answer 2

如果您需要使用二叉树来解决这个问题，那么没有什么可以说您不能复制分支或节点。将猫答案节点放置在多个决策集的末尾。或者问两次捕食者问题--一次是使用者对哺乳动物说“是”，一次是使用者说“不”。

当然，如果采用这种策略，也存在优化和效率方面的问题，但是也有一些解决特定问题的方法。(例如，如果您担心决策树的存储空间，那么创建分支或节点或指向不可变对象/声明的两个指针)。

Answer 3

我相信您要寻找的是更常见的决策树，特别是用于分类。然后，您可以使用像C4.5这样的算法来学习如何对您的问题进行有效分类。