學(xué)習(xí)材料

決策樹

決策樹是指，以操作或行為為中間結(jié)點(diǎn)，以情況或決策為終端葉子結(jié)點(diǎn)的樹狀信息結(jié)構(gòu)，可用于復(fù)雜情況的分析和復(fù)雜決策的輔助工具。示例：

此處物品數(shù)量是葉子結(jié)點(diǎn)的情況，是否需要背包是葉子結(jié)點(diǎn)的決策。

事件空間

每個(gè)結(jié)點(diǎn)的所有后代葉子結(jié)點(diǎn)構(gòu)成一個(gè)組（集合），這個(gè)組稱為事件空間，或事件域。例如上一示例中，下雨結(jié)點(diǎn)的事件空間是{帶傘和午餐，帶傘不帶午餐}，不下雨結(jié)點(diǎn)的事件空間是{不帶傘帶午餐，不帶傘不帶午餐}或者{不帶傘}，下雨且下午有課結(jié)點(diǎn)的事件空間是{帶傘和午餐}。

事件空間的重疊性

事件空間是可能重疊的。例如改寫上一個(gè)示例，決策樹中每個(gè)葉子結(jié)點(diǎn)都只記錄攜帶物品個(gè)數(shù)，那么下雨結(jié)點(diǎn)事件空間為{攜帶物品個(gè)數(shù)=2，攜帶物品個(gè)數(shù)≤1}，不下雨結(jié)點(diǎn)事件空間為{攜帶物品個(gè)數(shù)≤1}。

為方便區(qū)分，定義事件空間中所有結(jié)點(diǎn)的個(gè)數(shù)為事件空間的結(jié)點(diǎn)數(shù)，事件空間中所有不同的結(jié)點(diǎn)個(gè)數(shù)稱為情況數(shù)。例如，上一示例的根節(jié)點(diǎn)事件空間的結(jié)點(diǎn)數(shù)是3：{下雨且有課，下雨但沒課，不下雨}，而情況數(shù)是2：{物品數(shù)量=2，物品數(shù)量≤1}。

作業(yè)1

1.繪制一個(gè)你生活中進(jìn)行決策的決策樹，需要2-3層（即可能進(jìn)行至少兩次相連的判斷）。

2.思考題：假設(shè)你在某異國旅游，現(xiàn)在遇到了一個(gè)岔路口，前方有兩條路，你并不知道去A地該走哪一條。路口有兩個(gè)守衛(wèi)，其中一個(gè)永遠(yuǎn)說真話，另一個(gè)永遠(yuǎn)說假話，但你并不知道誰說真話。你只能問一個(gè)問題，并且這個(gè)問題只能由一個(gè)守衛(wèi)回答，他只能回答是或否。你應(yīng)該如何提問來判斷正確的道路？這個(gè)題目的解答和決策樹有什么關(guān)系？

反向決策樹

決策樹分析在正向討論時(shí)一般很簡單，有時(shí)甚至顯得多此一舉。但是如果需要進(jìn)行反向的決策樹分析，不借助它分析就比較困難了。

作業(yè)1的第二道題目的答案是，你應(yīng)該隨意問一個(gè)守衛(wèi)：“如果我問另外一個(gè)守衛(wèi)去A應(yīng)該走哪條路，他會回答走左邊這條路，是還是否？”，然后如果他回答是，你就走右邊的路，如果回答否，就走左邊的路。

這個(gè)謎題在各種游戲中出現(xiàn)并飽受詬病，很多人指責(zé)其是一種對腦洞，和作者腦洞對上了就會做，而對不上就不會做。但是，決策樹分析可以讓這樣的題目不再是一種無邏輯的思考，而是一種逐步的推理，題目的求解是符合邏輯規(guī)律的。

我們構(gòu)造一個(gè)提問的決策樹。因?yàn)橹荒軉栆粋€(gè)問題，因此決策樹只有一層；而問題必須用是否來回答，所以這個(gè)決策樹結(jié)點(diǎn)只有兩個(gè)子節(jié)點(diǎn)。我們希望通過這個(gè)問題來區(qū)分兩種情況：左邊的路通向A，和右邊的路通向A。因此這棵樹的兩個(gè)子結(jié)點(diǎn)必然就是這兩種情況。注意到這里決策樹的性質(zhì)發(fā)揮了作用：如果我們考慮四個(gè)情況：左邊守衛(wèi)說真話且左邊路正確，右邊真話右邊正確……，那么這四個(gè)情況中左側(cè)路正確的兩種情況在同一個(gè)分支之下，這兩種情況中一種是左邊守衛(wèi)說真話，另一種是右邊守衛(wèi)說真話，也就是說，這個(gè)問題一定不能判斷出哪個(gè)守衛(wèi)說了真話。所以我們構(gòu)造的問題必須在某個(gè)守衛(wèi)說真話和假話的兩個(gè)情況下得到相同的結(jié)果，那么這個(gè)結(jié)果不依賴守衛(wèi)的發(fā)言屬性，一定就來自于路的正確屬性。在此基礎(chǔ)上考慮問題就容易很多，我們只需要讓守衛(wèi)的真假話屬性互相抵消或者構(gòu)成某些穩(wěn)定的不變量，就可以做到無法問出誰說真話。除了上文提到的解答，此題還可以如此解：詢問任意一個(gè)守衛(wèi)：“如果我問你左邊的路是否通向A，你會怎么回答？”，然后若回答是則走左邊，否則走右邊。

作業(yè)2

觀看視頻

你可以自己思考視頻給出的題目，也可以直接看答案。作業(yè)要求是：請假設(shè)你從未學(xué)過二進(jìn)制，也不會想到原題解答中讓2=0這樣相加的方法，但是學(xué)過了決策樹分析，借此分析題目，給出你的解答。（提示：你需要枚舉一些情況，這樣做出的解答將會不如原視頻的解答美觀，但是在借助決策樹時(shí)更容易想到。注意，你的決策樹的每個(gè)中間節(jié)點(diǎn)不一定只有兩個(gè)子節(jié)點(diǎn)。）

注：如果你已經(jīng)發(fā)現(xiàn)了一些最終解答的性質(zhì)，但是懶得進(jìn)行枚舉，寫下這些性質(zhì)即可。性質(zhì)越多，進(jìn)行枚舉的情況就越少越簡單。

總結(jié)和拆分

上述知識體系涉及到的概念：決策樹，事件空間，事件空間的結(jié)點(diǎn)數(shù)，事件空間的情況數(shù)，反向決策樹。關(guān)系如下：

作業(yè)3

進(jìn)行反向決策樹分析時(shí)，是否可能出現(xiàn)事件空間重疊的現(xiàn)象？如何利用結(jié)點(diǎn)數(shù)與情況數(shù)的關(guān)系解決這個(gè)問題？觀看視頻

的問題部分，首先自行思考問題，嘗試運(yùn)用決策樹分析來解決問題，然后觀看視頻的解答部分，并完成以下任務(wù)：

1.分析并證明，如果你完整解決了這個(gè)問題，那么你一定不可能知道Ozo和Ulu哪一個(gè)代表“是”。（提示：仿照作業(yè)1第二題的分析）

2.繪制這個(gè)問題解答的決策樹，找出其中的事件空間的重疊。

3.對問題進(jìn)行這樣一個(gè)修改：如果前提條件改為“在日期為奇數(shù)的日子，所有人都說真話；在日期為偶數(shù)的日子，三位首領(lǐng)按照原題的規(guī)律說話。你不知道今天的日期是不是奇數(shù)。如果是，那么你可以隨意贈送禮物，都視為成功，但是如果不是，你仍然需要給正確的首領(lǐng)贈送禮物?！保@個(gè)題目還能否解答？如果可以，給出你的解答，如果不能，請說明原因。記得使用決策樹分析。（提示：現(xiàn)在決策樹本身事件空間的情況數(shù)有多少？結(jié)點(diǎn)數(shù)有多少？第一個(gè)問題的回答是是或者否，這兩個(gè)結(jié)點(diǎn)的事件空間的結(jié)點(diǎn)數(shù)和情況數(shù)分別是多少？這樣的決策樹是否可能存在？）

思考題：嘗試?yán)脹Q策樹分析的思路，命制一道智力謎題。