贪心算法和决策树

今天，我想解决一个“排排坐、分果果”的问题[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