学习材料

决策树

决策树是指，以操作或行为为中间结点，以情况或决策为终端叶子结点的树状信息结构，可用于复杂情况的分析和复杂决策的辅助工具。示例：

此处物品数量是叶子结点的情况，是否需要背包是叶子结点的决策。

事件空间

每个结点的所有后代叶子结点构成一个组（集合），这个组称为事件空间，或事件域。例如上一示例中，下雨结点的事件空间是{带伞和午餐，带伞不带午餐}，不下雨结点的事件空间是{不带伞带午餐，不带伞不带午餐}或者{不带伞}，下雨且下午有课结点的事件空间是{带伞和午餐}。

事件空间的重叠性

事件空间是可能重叠的。例如改写上一个示例，决策树中每个叶子结点都只记录携带物品个数，那么下雨结点事件空间为{携带物品个数=2，携带物品个数≤1}，不下雨结点事件空间为{携带物品个数≤1}。

为方便区分，定义事件空间中所有结点的个数为事件空间的结点数，事件空间中所有不同的结点个数称为情况数。例如，上一示例的根节点事件空间的结点数是3：{下雨且有课，下雨但没课，不下雨}，而情况数是2：{物品数量=2，物品数量≤1}。

作业1

1.绘制一个你生活中进行决策的决策树，需要2-3层（即可能进行至少两次相连的判断）。

2.思考题：假设你在某异国旅游，现在遇到了一个岔路口，前方有两条路，你并不知道去A地该走哪一条。路口有两个守卫，其中一个永远说真话，另一个永远说假话，但你并不知道谁说真话。你只能问一个问题，并且这个问题只能由一个守卫回答，他只能回答是或否。你应该如何提问来判断正确的道路？这个题目的解答和决策树有什么关系？

反向决策树

决策树分析在正向讨论时一般很简单，有时甚至显得多此一举。但是如果需要进行反向的决策树分析，不借助它分析就比较困难了。

作业1的第二道题目的答案是，你应该随意问一个守卫：“如果我问另外一个守卫去A应该走哪条路，他会回答走左边这条路，是还是否？”，然后如果他回答是，你就走右边的路，如果回答否，就走左边的路。

这个谜题在各种游戏中出现并饱受诟病，很多人指责其是一种对脑洞，和作者脑洞对上了就会做，而对不上就不会做。但是，决策树分析可以让这样的题目不再是一种无逻辑的思考，而是一种逐步的推理，题目的求解是符合逻辑规律的。

我们构造一个提问的决策树。因为只能问一个问题，因此决策树只有一层；而问题必须用是否来回答，所以这个决策树结点只有两个子节点。我们希望通过这个问题来区分两种情况：左边的路通向A，和右边的路通向A。因此这棵树的两个子结点必然就是这两种情况。注意到这里决策树的性质发挥了作用：如果我们考虑四个情况：左边守卫说真话且左边路正确，右边真话右边正确……，那么这四个情况中左侧路正确的两种情况在同一个分支之下，这两种情况中一种是左边守卫说真话，另一种是右边守卫说真话，也就是说，这个问题一定不能判断出哪个守卫说了真话。所以我们构造的问题必须在某个守卫说真话和假话的两个情况下得到相同的结果，那么这个结果不依赖守卫的发言属性，一定就来自于路的正确属性。在此基础上考虑问题就容易很多，我们只需要让守卫的真假话属性互相抵消或者构成某些稳定的不变量，就可以做到无法问出谁说真话。除了上文提到的解答，此题还可以如此解：询问任意一个守卫：“如果我问你左边的路是否通向A，你会怎么回答？”，然后若回答是则走左边，否则走右边。

作业2

观看视频

你可以自己思考视频给出的题目，也可以直接看答案。作业要求是：请假设你从未学过二进制，也不会想到原题解答中让2=0这样相加的方法，但是学过了决策树分析，借此分析题目，给出你的解答。（提示：你需要枚举一些情况，这样做出的解答将会不如原视频的解答美观，但是在借助决策树时更容易想到。注意，你的决策树的每个中间节点不一定只有两个子节点。）

注：如果你已经发现了一些最终解答的性质，但是懒得进行枚举，写下这些性质即可。性质越多，进行枚举的情况就越少越简单。

总结和拆分

上述知识体系涉及到的概念：决策树，事件空间，事件空间的结点数，事件空间的情况数，反向决策树。关系如下：

作业3

进行反向决策树分析时，是否可能出现事件空间重叠的现象？如何利用结点数与情况数的关系解决这个问题？观看视频

的问题部分，首先自行思考问题，尝试运用决策树分析来解决问题，然后观看视频的解答部分，并完成以下任务：

1.分析并证明，如果你完整解决了这个问题，那么你一定不可能知道Ozo和Ulu哪一个代表“是”。（提示：仿照作业1第二题的分析）

2.绘制这个问题解答的决策树，找出其中的事件空间的重叠。

3.对问题进行这样一个修改：如果前提条件改为“在日期为奇数的日子，所有人都说真话；在日期为偶数的日子，三位首领按照原题的规律说话。你不知道今天的日期是不是奇数。如果是，那么你可以随意赠送礼物，都视为成功，但是如果不是，你仍然需要给正确的首领赠送礼物。”，这个题目还能否解答？如果可以，给出你的解答，如果不能，请说明原因。记得使用决策树分析。（提示：现在决策树本身事件空间的情况数有多少？结点数有多少？第一个问题的回答是是或者否，这两个结点的事件空间的结点数和情况数分别是多少？这样的决策树是否可能存在？）

思考题：尝试利用决策树分析的思路，命制一道智力谜题。