algorithm - 决策树和算法选择

Question

我的家庭作业要求我编写一个类似 Akinator 的游戏(仅使用函数范式)，在这个游戏中，计算机会问我一些关于我正在想的人的问题，并且必须猜出它是谁。我有一个大约有 20 个人的数据库，每个人都有大约 10 个问题，他们可以回答 "true"或 "false" .

我被要求构建定义为最小(深度)的决策树:

<Tree> ::= leaf(<List[Atom]>) %list of persons
| question(<Atom> true :<Tree> false :<Tree>) .

有人建议我用一个简单的算法来做到这一点，其中树的下一个节点代表真假数最接近的问题。我必须编写一个至少与这个算法一样高效的算法。因此，我在互联网上查找了更好的算法，并发现了一些算法，例如 C4.5 和 ID3。

我的问题是我可以使用哪种算法比我为作业建议的算法更好？ (一个对于我的要求来说不是太复杂的吗？)

Answer 1

算法 C4.5 和 ID3 都是贪心算法，对于如此简单的真假数据，它们最终会构建与您解释的简单解决方案相同的树。贪心算法做出局部最优选择，但可能不会构建全局最优树。一般 build globally optimal trees is NP-Complete .有一些算法试图改进贪心算法，但总的来说它们非常复杂或/并且效果不佳。参见，例如 chapter 5.4 of a survey article .