貪心演算法和決策樹

今天，我想解決一個「排排坐、分果果」的問題[1]。

有N個小朋友排成一條線，每個小朋友都有一個分數（我們可以認為是考試成績），按照如下規則給所有的小朋友分發糖果：每個小朋友至少分到了一顆糖果；如果一個小朋友的得分比旁邊的小朋友高，則他應比旁邊那位小朋友分到更多的糖果。問題來了，在限定的規則下最少需要幾顆糖果？

直覺上，這個問題不難，然而它在在線評測網站上被歸類為「Hard」的問題，提交通過率不到30%，似乎暗示它並不能按直覺來解決（聰明人/經受過演算法訓練的人產生的直覺排除在外）。

即便如此，依然選擇根據直覺來分析一下這個問題：小朋友獲得的糖果數量是根據局部信息（相鄰的小朋友）就可以確定的，所以可以使用貪心策略來完成這個問題，通過分別考察左鄰居和右鄰居的兩次遍歷過程，以O(N)的時間和O(N)的空間完成整個問題的求解。

圖１ 解決分糖問題的代碼示例

根據此平凡的想法寫出代碼提交。十分意外的是，作為一個Medium難度都經常卡住的演算法渣，這一次直接通過並且運行速度超過了97%的歷史提交，這應該是我AC過程最輕鬆的Hard類別問題。不過考慮到這是一道編號十分靠前的老題，現在的速度快可能僅僅是因為伺服器CPU相比過去做了升級吧。

總結一下貪心策略：這是一種在每一步都做出局部最優選擇的演算法。在很多問題中，貪心策略一般不能獲得全局最優解[2]，然而這道題算是一個例外，因為它只需要局部信息就能求出全局最優解。

寫到這裡，我並不是想講一道演算法題。

近來總是在晚上睡覺時經歷「睡不著-思考人生-睡不著-數數字-還是睡不著-肚子餓了-更加睡不著」的循環，因為對自己過往的一些人生選擇產生了一些懷疑。在這些日子裡，時常反思自己這兩年做出的選擇，似乎就像是在人生路徑上運行了一遍貪心演算法，總是在偏好做一個激進卻可能不長遠的選擇。有時候會感到一絲後悔，但也深知，後悔毫無用處，畢竟人生不是解演算法題，沒有第二次提交的機會。

我有時候會想，人的一生，就像是在一棵決策樹上自頂而下前進，每一個節點只有一次選擇的機會，選擇了就只能繼續往下走，沒有回溯，更不可能遍歷。若再細想，決策樹是一個分類預測模型，待分類的樣本所有的屬性從一開始就是全知的，因此一個樣本會經過的節點和分叉從開始就已確定。而人不一樣，是人主動地選擇了每一次分叉時前進的方向，每一次選擇給人添加了與之相關的屬性，這些屬性連同最終到達的結果，形成了一個單獨的樣本。

如果人在每一次選擇的過程中，真的參考了一棵決策樹，這棵樹是從哪兒來的？顯然，它必然是經過一定的「訓練」過程得到的，它的訓練集就是我們通過各種方式得知的人，而它的驗證集就是我們自己，雖然這個驗證集實在太小了。如果我們生成的決策樹總是在驗證集上表現不佳，那就應該檢查生成它的訓練演算法是否遭遇了偏差或是過擬合，並對應地選擇方法去改進。不嚴謹地說，在演算法實現正確的前提下，增大訓練集的數量對減小誤差一般不會有負面作用。但是，訓練集的類別平衡是十分重要的，一味增大某一類別的樣本會對模型的準確度有負效應。所以，在人生選擇面前，多聽多看總沒有錯，並且，在喝下成功者的雞湯的同時，也得多聽聽失敗者的抱怨。

想了一大堆，寫了一點點，今天的故事就暫且講到這吧。

思考題（Optional）

在圖1出現的代碼中，每一行均不超過79（或80）字元，這一數字也是大多數語言都會推薦的規範。從計算機相關硬體的發展歷程考慮，為什麼會有這樣的編碼習慣？

考慮帶有預剪枝的C4.5決策樹的訓練過程，貪心策略可能在哪些步驟使用？對泛化性能可能有什麼影響？

參考文獻

[1] Candy-Leetcode. https://leetcode.com/problems/candy/description

[2] Greedy Algorithm. https://en.wikipedia.org/wiki/Greedy_algorithm

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！