算法告诉你,拖延症会让效率变高吗

开了一算法专栏,整理了我当大学助教和面试算法的过程中,比较有意思的话题。预计每隔周出一篇原创文章,更新于微博/知乎/公主号@甜菜欣欣,欢迎反馈意见,共同交流学习。

当代年轻人,面临的一大难题就是拖延症

想到有那么多事情要做,赶紧刷会儿手机压压惊。任务总是拖到最后一刻,相信自己一定能急中生智化险为夷。逃避可耻但有用,一言不合就通宵。截止日期的前一晚,效率高到突破天际。

那么,这样的时间安排到底合理吗?最后一刻突如其来的求生欲,能会给你最高的效率吗?算法告诉你答案。

首先,对问句里的概念下个更为精确的定义——

假设现在有n个任务,每个任务完成的时间是一个单位的时间(比如一小时),分别有对应的截止时刻,还有按时完成所能获得的分数(一个大于零的实数)。如果一个任务在截止时刻前被完成,就能累计对应的分数,否则不加分。现在要安排这些任务在整数的时间点开始,每个单位时间最多只能进行一项任务,求一种算法能解出最优的计划,得到最多的分数。

某拖延症欣欣给出的算法如下——

首先,按分数高低给任务排序。然后从分值最高的任务开始,对于每个任务,都分别安排在任务截止时刻前的最后一个空闲的单位时间块里。

先说结论。这个拖延症算法,解出来的结果是最优的。也就是说,这个计划确实能安排得下最多的任务。惊不惊喜,意不意外?

有的朋友可能看出了,这个算法属于贪心算法(Greedy Algorithm),即每一步都只考虑当前情况下最优的选择。就好像去吃自助餐的时候,先跑去吃最好吃的东西一样;或者找给别人零钱的时候,先给十块钱的纸币,剩下的用五块钱,然后一块钱和硬币,最为方便。

当贪心算法满足下面两个条件,就能得到问题的整体最优解——

1)贪心选择性质(Greedy-Choice Property):问题的整体最优解可通过不断选择局部的最优解来得到;

2)最优子结构性质(Optimal Substructure):问题的整体最优解包含了它的子问题的最优解。

回到由欣欣命名的拖延症算法。直觉的解释是,时间越靠前越宝贵,所以要优先安排最贵的任务,又不舍得安排到最前面耽误了其它稍便宜的任务,那就优先安排但尽量安排得晚一些。而贪心算法的严谨证明,还需多花一点力气。

为了简化问题,只考虑那些把时刻0到时刻n都排满的计划。因为任何的最优解,必然是从一开始就排满的。如果一个计划在时刻0到时刻n有空闲的时间块,那么把时刻n以后的任务往前填,必然只会增加按时完成的任务数量和分值,得到更优的解。

于是问题被简化成了只有n个任务和n个时间块,注意任务数和时间块的数量相等了。假设题目允许不把一个任务安排到任何时间点,因为任务无论如何都无法按时完成的话安排便无意义,但方便起见我们还是把这个任务放置到最末的空闲时间块。

我们锁定一个最优解的安排,方便起见将其标记为Q。

第一步,证明“贪心选择性质”成立。需要证明对于任何一个情况,如果把分值最高的任务叫做T,把T被拖延算法安排到的时间块记作t,那么存在某个最优解Q*把任务T安排到了时间t。

证明开始。如果在最优安排Q*里,任务T已经被安排到了时间t,那么啥也没做上面那句话就成立了。否则若时间t安排了另一个任务T’,而任务T被安排到了另一个时间t’,我们则可以构造一个新的解Q’,在这个解里交换任务T和T’的位置。然后分类讨论来证明Q’也是最优解:

情况一,时间t早于任务T的截止时刻,且在安排Q*里任务T得到了按时完成的加分。那么时间t’早于t,因为任务T’已经被安排到了再晚就没有加分的时间。交换T和T’之后,根据分类条件T仍有加分,而T’更早完成了,总分值只会增加而不会降低。

情况二,时间t早于任务T的截止时刻,且在安排Q*里任务T没有得到加分,那么时间t’要晚于t。交换T和T’之后,最坏结果是错过了低分值任务却额外获得了高分值,任务总分值只会增加而不会降低。

情况三,时间t晚于任务T的截止时刻,那么说明任务的截止时刻前没有空余时间了,任何安排都无法得到任务T的分值。而根据算法,t是最后一个空余的时间块,所以t’早于t。交换任务使得低分值任务T’被提到更前面,有可能额外得到任务T’的分值,总分值可能增加而不可能降低。

所以Q’在这三种情况下都是最优解,而Q’任务T安排到了时间t。每当我们做出一个贪心选择,都会得到一个完全独立不受限制的子问题,直到算法结束。第一步证毕。

第二步,证明“最优子结构性质”成立。把一个任务安排到一个时间块,剩下的任务和剩下的时间块就可组成一个子问题。我们需要证明,如果在(n-1)个任务和(n-1)个时间块组成的子问题里已有最优的计划,那么把额外的一个任务安排在额外的一个时间块,所得到的还是最优的计划。

这部分证明更短一些。假设子问题里的某个计划能得到分值S,而最优计划能得到分值S*;在更大的问题里多安排一个任务能总共得到T,而最优计划能得到分值T*;把额外的那个任务安排在额外的那个时间块能得到的分数标记为B。

T = B + S (对于任一计划)
T* = B + S* (对于最优计划)

已知S ≤ S*,所以T ≤ T*。最优计划还是最优计划,就是没办法。

至此我们证明了,拖延症算法能让我们完成最多最重要的事情。当然,实际生活中最好还是不要把事情拖到最后一刻去做,现实往往是一个任务没做就完蛋了,唯一的方法是使劲做。

如果给上面那个问题稍加变化,每个任务不是单位时间而是可以为任意整数时间长度,猜猜看还能用贪心来解吗?这道题被收录在Leetcode #253 会议室二(Meeting Room II),是最为经典的算法面试题之一。以后有时间补充证明思路~

关于贪心算法,最后简短提几个点。

1)贪心算法不是某个具体的算法,而是一大类算法的总称。粗略地说,凡是啥也不管狂在局部选最优解的都可称作贪心算法。

2)能用贪心算法解决的问题,当前决策必须不能对之前的选择有依赖,只可和当前的状态有关。往往问题的不同部分之间关系不太紧密,尤其是时序上的关系。

3)贪心算法的“最优子结构性质”很多时候容易和动态规划(dynamic programming)里的概念弄混。如果没有听说过动态规划,不用慌,可先跳过这段。动态规划和贪心算法非常不一样,动态规划会同时计算互斥的一些状态,而贪心永远只有一种状态、一种可能性,并且不会撤销回到之前的状态。

4)贪心算法作为基础算法思想,不仅在生活中,在计算机世界里也有广泛的应用。一个比较经典的例子是哈夫曼编码(Huffman Coding),根据字符出现的频率构造出一棵二叉树,然后用它来压缩数据,非常酷炫。

评论区

  1. 山野愚人居 2019年9月22日 回复

    太深奥,我等学渣看不懂了……

  2. 响石潭 2019年8月31日 回复

    感谢分享,学习

发表评论

电子邮件地址不会被公开。 必填项已用*标注