我的家庭作业要求我编写一个类似 Akinator 的游戏(仅使用函数范式),在这个游戏中,计算机会问我一些关于我正在想的人的问题,并且必须猜出它是谁。我有一个大约有 20 个人的数据库,每个人都有大约 10 个问题,他们可以回答 "true"
或 "false"
.
我被要求构建定义为最小(深度)的决策树:
<Tree> ::= leaf(<List[Atom]>) %list of persons
| question(<Atom> true :<Tree> false :<Tree>)
.
有人建议我用一个简单的算法来做到这一点,其中树的下一个节点代表真假数最接近的问题。我必须编写一个至少与这个算法一样高效的算法。因此,我在互联网上查找了更好的算法,并发现了一些算法,例如 C4.5 和 ID3。
我的问题是我可以使用哪种算法比我为作业建议的算法更好? (一个对于我的要求来说不是太复杂的吗?)
最佳答案
算法 C4.5 和 ID3 都是贪心算法,对于如此简单的真假数据,它们最终会构建与您解释的简单解决方案相同的树。贪心算法做出局部最优选择,但可能不会构建全局最优树。一般 build globally optimal trees is NP-Complete .有一些算法试图改进贪心算法,但总的来说它们非常复杂或/并且效果不佳。参见,例如 chapter 5.4 of a survey article .
关于algorithm - 决策树和算法选择,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33842540/