人生不可 DP，但别永远贪心

声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2019/04/24/life-cannot-dp-but-dont-be-always-greedy/

目录

1. 前言
2. 名词解释
3. 多阶段决策问题
4. 个体的贪心
5. 上帝的无力
6. 随机扰动
7. 结束语

前言

这是一篇在 2018 年 12 月份起草的文章，当时 AlgoCasts 刚上线两个多月，心中实有许多想表，这是其中一篇。当时写了大概一半，然后为了完成当天的视频制作，就暂时保存草稿。不曾想，耽搁至今。今天趁着刚把 Plan 150 完成，坐下来安静地把剩下的一半写完，希望还能找到几个月前如泉涌般的思绪。

名词解释

考虑到可能会有非计算机专业/行业的人阅读本文，本着负责的态度，还是把标题里的两个名词简单解释一下。这真的不是在凑字数，已经知道的读者可以跳过。

第一个要解释的名词是 DP，它是 Dynamic Programming 的缩写，中文是「动态规划」，一种解决问题的方法。它的思想非常简单：在求解一个复杂问题时，先把它分解为一系列较简单的子问题，然后求解子问题并存储子问题的解，进而利用这些子问题的解去求解原问题。这个思想中隐含了一个不是那么明显的条件，即我们可以利用子问题的解去计算原问题的解，并不是所有的问题都能满足这个条件。尤其对于最优化问题，最终我们要求解的全局最优解，并不总是可以由一系列子问题的最优解来计算得到。对于这类问题，我们就无法使用「动态规划」进行求解。反之，如果全局最优解可以由一系列子问题的最优解来计算得到（这个描述是递归的，即子问题的最优解也可以由一系列子子问题的最优解计算得到），那么我们就可以使用「动态规划」进行求解，并且这类问题称为具有最优子结构的问题。

第二个要解释的名词是「贪心」，标题里「贪心」呼应 DP，它指的是贪心算法（Greedy Algorithm），同样是一种解决问题的方法。它的思想也很简单：在求解一个多阶段决策问题时，我们每一步都做出在当时看起来最优的决策或选择，做完一次决策后，再用同样的策略去解决接下来的子问题。贪心算法无法保证求得全局最优解。

多阶段决策问题

顾名思义，多阶段决策问题（multi-stage decision problem）可以划分为多个相互联系的阶段，一般来说，每个阶段都有若干决策可供选择，而每个阶段具体做出的决策往往会影响下一阶段的可选决策集合。对于这类问题，我们最后往往需要求解一个决策序列，这个决策序列使得某个收益函数最大化，或使得某个代价函数最小化。

OK，铺垫了那么多，接下来要开始谈人生了。

首先我想说，任何一个个体的一生都是一个复杂得难以建模的过程。但这里我还是尝试将它进行极大的简化，将个体的一生看成一个多阶段决策过程，以此得出一些哪怕只是有限正确（Bounded Correctness。前有 Herbert Simon 提出 Bounded Rationality，今有 Hawstein 生造 Bounded Correctness）但有意思的结论。在时间维度上，我们可以把个体的一生分为若干阶段，阶段粒度可大可小，阶段数量可多可少，甚至可以将一些小阶段忽略，就像物理教材中把足够光滑表面的摩擦力忽略不计一样。在每个阶段中，往往要面临许多的选择，比如很多中国学生曾经面对过的灵魂拷问：我是选择上清华还是上北大？每个阶段做出选择/决策后，根据选择/决策的不同，我们会进入不同的下一阶段。这个过程不断重复，直到生命终结。

从这个视角来看，个体一生做出的所有选择，按时间先后可以形成一个大小为 N 的决策序列，这个序列就是他对人生这个多阶段决策问题的解。那么，这道题我们到底解得怎么样呢？

个体的贪心

我们来看一下，个体是如何解人生这个多阶段决策问题的。当然，我不会说所有人都在使用同一策略，但如果回顾自己、周围的人以及历史上许多人物，在不同阶段面对不同选择时，有相当大一部分人都在使用贪心策略。由此，我可以做一个粗浅的推断：很大比例的个体，甚至可以说是绝大部分的个体，在面临选择需要做出决策时，依据的是贪心策略。也就是说，当有一堆选择放在我们面前时，我们总是倾向于选择最优的那个。听起来没任何毛病，对吧。仿佛这件事就是烙印在我们基因中的默认设置。

当然了，情况比这要复杂一些。因为对于不同的个体，最优指的是不同的东西。即每个人在自己心中有一个属于他自己的收益函数或代价函数，所以把不同人放到同一个阶段，给他们一模一样的选项，他们也会做出不同的选择。因此，这里规定一下，当我们在讨论最优时，指的是针对具体个体的最优，也就是对于正在读文章的你而言的最优。听起来好像要变得越来越复杂了，其实也不会。个体有千千万，但收益函数和代价函数其实非常有限。

贪心策略，对我们来说意味着什么呢？意味着上小学的时候好好读书/做题/考试，尽我们所能去上个好中学；意味着上中学的时候好好读书/做题/考试，尽我们所能去上个好大学；意味着上大学的时候好好读书/做题/考试，尽我们所能去找个好工作；意味着工作后兢兢业业、任劳任怨，争取升级，或者在跳槽时可以拥有一个比较好看的履历，因而可以拿到另一份更好的 offer…老铁，听起来还是没有任何毛病，对吧。这应该是绝大部分人的决策路径，而且这么走下来，也会有一个还不错的结果（收益）。这也是贪心算法所揭示的，如果每一次总是选择你眼前的最优选项，最后你能到达某个局部最优，至于它是不是全局最优，就没人能保证了。并且这个局部最优到底有多优，极大地依赖于你的初始状态：你生在哪个国家、哪个城市、什么样的家庭、有怎样的父母等等。举个简单的例子，如果地球上遍布高低不平的山峰，而每个人出生后的目标就是爬得尽可能高。那么如果使用贪心算法，个体能爬到的最大高度基本上完全取决于一开始你出生在哪座山脚下。如果你出生在一座小山丘旁边，并且使用贪心算法做决策，每次都选择你眼前的最优路径前进，那么你必然会爬上你家旁边的那座小山丘，它的高度就是你的天花板。嗯，我们说的是天花板，因为同样的情况下，很多人连那座小山丘的山顶都爬不到；而如果你出生在珠穆朗玛峰的山脚下，贪心算法决定了你的天花板就是珠峰的高度。当然，爬不爬得上去就是另一个问题了。

这几年，不知道谁又造了个词叫「阶层固化」来焦虑大众。在我看来，阶层固化不过是一直使用贪心策略的情况下，个体的人生天花板极大依赖于个体初始状态的表象而已。其实阶层并没有固化，只不过大家都在使用贪心策略，流动缓慢。把时间拉长看几代人，上一代个体做出的努力，会给下一代提供一个更好的初值。当然下一代人如果还是只使用贪心策略，人生天花板同样很大程度上只依赖于他拿到的初值。

上帝的无力

既然贪心策略会让我们陷入局部最优，那我们可以换个策略吗，比如 DP。很可惜，人生不可 DP。

人生不可 DP 包含两层含义。第一，我们不能把摆在我们面前的每种选择都试一遍，然后记录最优。每次我们都只能做出一个选择，然后向前走，无法回头，无法重新选择历史路径。第二，也是最根本的，人生这个问题并不具有最优子结构，全局最优解并不能由一系列子问题最优解计算得到。也就是说，即使存在一个全知全能的上帝，让他帮你算一下人生最优解。他除了暴力穷举你的所有人生路径外，没有办法更快地帮你找到最优路径。

So sad…

这么看来，我们是没有确定的方法去达到个体人生中的理论最优解了。这样的话，我们还有什么可做的么？有，引入随机扰动。

随机扰动

搞最优化理论的人都知道，可以通过加入随机扰动来逃离局部最优。这么做虽然不能百分百避免陷入局部最优，也无法保证可以找到全局最优，但往往能得到一个更好的解。人生其实也是这样，每一步都采用贪心算法，确定性最大，心里也最踏实（我不知道上帝掷不掷骰子，但我知道大部分人讨厌不确定性）。但绝大多数时候，这样的人生都陷入了局部最优，到达了一个从山脚下就已经看到顶的小山坡。而如果你愿意为你的人生加入一些随机扰动，在某些阶段选择一个对你的收益函数来说并非最优的选项，甚至去选一个原来根本不在你考虑范围的选项（你懂的，很多时候我们只会看到我们想看到的东西），这些选项具有更多的不确定和未知，那么你就为你的人生注入了更广阔的可能性。这些可能性有可能「好」也有可能「不好」，没人知道。这条新路径上会出现什么，会遇到谁，也更不确定。一切都需要自己去探索。

随机扰动有怎样的表象呢？

上学时不是把所有的时间精力都拿来学习考取 100 分争当第一名。如果你喜欢音乐，试着认真学习一样乐器或尝试组个乐队；如果你爱好阅读，试着组个读书协会，把志同道合的人约来一起看书讨论；如果你思想深刻观点尖锐，那尝试创办个学报/或持续地输出文章，指点江山，激扬文字；如果你会编程，可以折腾个小网站，展示你的爱好或你的作品；可以开发个 App 解决身边人的一点小问题；又或者你有喜欢的人，去表白去谈一场恋爱…

工作时不必总是去给钱最多或技术最好的公司，也许仅仅因为你觉得它很 cool 就去这家公司，又有何不可呢？如果有个不错的机会，又何必因为是年底然后就非要等拿完年终奖再走？如果有个不错的想法，何必因为待在大厂收入不错 title 好听，就束手束脚不敢一试？最后，又何必非要去一家公司，自己出来做点小事情，也未尝不可…

举上面的例子，并不是说它们都是值得一试的，也无法保证会有更好的结果。但如果一直以来，你都使用贪心算法去做决策，不妨偶尔也为自己加入点随机扰动，不去选择眼前所谓「最优」的选项，为自己的人生加入一些不确定性，同时也为自己打开更多的可能性。

结束语

最后，希望我们能为自己的人生加入一些随机扰动，而不总是使用贪心策略去选择眼前的最优选项；希望我们能去拥抱不确定性，甚至主动为自己制造不确定性；希望我们的人生，有更多的可能性，而我们，能收获一个更好的解。