一类最优序列问题的贪心算法

在食堂打饭、在银行取钱、在火车站取票、在收银台结账……人生中不知有多少宝贵的时间浪费在了排队上。随着城市生活节奏的加快，如何节省客户排队等待的时间成了提高服务质量的一个关键因素。通过建立数学模型，数学家们逐渐发展出了一门叫作“排队论”的学科，专门研究排队的现象。现在，我们来考虑与排队有关的一个经典问题：队伍的顺序会影响平均排队时间吗？

答案是肯定的。下面这个简单而又极端的例子告诉我们，队伍的顺序不但会对平均排队时间产生影响，有时这种影响还会非常大。假设有A、B两个人要去银行办理业务，其中A办理业务只需要一秒，B办理业务则需要一个小时。现在，这两个人同时走进银行，却发现银行里只开了一个窗口。那么谁先办理更好呢？显然，让A先办更合理一些。若让A排在B前面，那么B只需要等上一秒就可以办理自己的业务了，平均每个人用了半秒的时间排队。但是，若A排在了B的后面，他就得足足等上一个小时才能办完自己一秒钟就能办完的事儿，平均每个人花在排队上的时间长达半个小时。

我们自然而然地提出这样一个算法问题：已知每个人办理业务所需要的时间，如何设计一个排队的顺序，能让平均排队时间最短？

如果队伍中某个人办理业务需要t分钟，那么他后面的所有人都要多等上t分钟，因此直觉告诉我们，应该尽量让办理时间较短的人排在前面。让我们来对比一下，遵循“小业务者优先”和“大业务者优先”这两种不同的原则，平均排队时间会相差多少。

假如银行窗口前有10个人，第一个人办理业务只需要1分钟，第二个人办理业务需要2分钟，以此类推，最后一个人办完业务得花10分钟的时间。若按照办理业务所需的时间由少到多排队，则10个人的排队等待时间总和为

0+1+(1+2)+(1+2+3)+…+(1+2+3+…+9)=165（分钟）

平均每个人的等待时间为16.5分钟。

如果这10个人按照所需时间从多到少的顺序排队，要办10分钟的站在最前面，只需1分钟的站在最后面，则他们排队总共花费

0+10+(10+9)+(10+9+8)+…+(10+9+8+…+2)=330（分钟）

平均等候时间为33分钟。

把办理时间较短的人排在前面，这种排队方案总是最好的吗？有没有可能出现一些很特殊的情况，使得业务办理时间长的人站在前面反而更好？事实上，这样的情况是不会发生的。我们可以严格地证明，这种“小业务者优先”、“按所需时间由少到多排队”的算法始终是正确的，不管队伍中有多少人，不管他们办理业务各自需要的时间是多少。

假设有一群人，他们以任意一种方式排好了队，但在队伍中有两个位置相邻的人，其中站在前面的那个人办理业务所需的时间比紧跟在他身后的那个人更长。不妨假设前面那个人办理业务需要a分钟，他身后的那个人需要b分钟。如果把他俩所站的位置交换一下，那么原来站前面的人现在跑到了后面，需要多等b分钟的时间；而原来站在后面的人现在则跑到了前面，少等了a分钟的时间。由于a比b更大，因此这两个人的等待时间之和变小了。但交换这两个人的位置显然不会影响到其他人的排队等待时间，因此所有人的等待时间总和也随之变小了。也就是说，只要队伍里出现了一前一后两个人，他们满足前者办理业务需要的时间比后者更多，那么交换这两个人的位置总能让平均每个人的等待时间变得更短。显然，当平均等待时间达到最短的时候，队伍里将不再有站错位置的人，也就是说整个队伍是按照办理业务所需时间由短到长的顺序排好的了。

或许大家已经发现，这个思路与我们日常生活中的直觉是一致的——让办事时间短的人插在队伍前面似乎是一件很合理的事。下次当你站在长龙般的队伍中焦急地等待时，突然冒出一个人对你说“我有急事要办，反正就一两分钟的事，就让我插在你前面吧”，或许你将会有一些新的看法。这确实是一个损人利己的恶行，但站在整体的角度来说却是有益的，因为它缩短了所有人的平均等待时间。

上面的最优排队顺序问题有一个非常有趣的应用。假如我们需要在一盘磁带上储存n条长度不同的数据供今后查询，那么以怎样的顺序储存这些数据，才能让读取数据平均所需的时间最短？这里，我们假设今后各条数据被访问到的概率都是均等的。注意，如果要访问磁带上的第i条数据，我们必须要先“快进”跳过前面i-1条数据，所需要的时间与前面i-1条数据的总长度是成正比的。最后你会发现，我们需要最小化的东西与刚才的排队问题是一样的。因而，最优的存储方案就是，将各条数据按长度由小到大的顺序依次储存在磁带上即可。

大家或许会注意到，这里有一个有趣的巧合：每次都把耗时最短的项放到最前面，所得的方案总的来说也是最快的。这种解决问题的策略背后的思想非常单纯：在每一步都简单地做出一个在某种意义上只满足于眼前利益的选择，并且指望最终得到的方案就是最好的方案。这种寻找最优方案的策略可谓是目光短浅，不顾大局，被人们形象地叫作“贪心算法”（greedy algorithm）。可不要小瞧贪心算法，利用它所得到的解往往不算差，并且算法思路非常清晰，实现起来也很简单，运行起来效率极高，因而在实践中常被用来代替真正的最优算法。而且，对于某些特殊的问题，贪心算法有可能正好就是最优算法！除了刚才所讲的问题外，这样的例子还有很多。下面这个问题则是又一个非常漂亮的例子。

印象中，我目前经历过的最忙的一天，恐怕要算2013年3月31日了。这是一个星期天。当天早晨7:30，我睁开双眼从床上坐起，理了一下当天要做的事情，立即崩溃了。我要在15:00之前提交语料库的句子抽取代码，完成代码需要4个小时左右。我要在16:00之前写完一篇稿子，而这至少得用2个小时的时间。我要在21:00之前完成第二天演讲用的keynote，这恐怕要花3个小时的时间。另外，我还得花半个小时在网上选购一台投影仪，11:00之前必须下单，否则第二天上午无法送到。我还要去火车站退一张火车票，12:00之后就没法退了，全程估计要用1个小时。最后，我还要和老婆一块儿完成一个愚人节特别项目，这一共需要大约4个小时。这个项目必须在23:30之前完成，否则就没法在4月1日凌晨第一时间上线了。总结起来，我要做的事情及它们的截止时间如下：

• 写代码，需要4个小时，15:00之前必须完成。

• 写稿子，需要2个小时，16:00之前必须完成。

• 制作keynote，需要3个小时，21:00之前必须完成。

• 选购投影仪，需要0.5个小时，11:00之前必须完成。

• 退火车票，需要1个小时，12:00之前必须完成。

• 做特别项目，需要4个小时，23:30之前必须完成。

洗漱完毕后，上午8:00就能正式开工。假设任意两个任务都不能同时进行，吃午饭和吃晚饭的时间可以忽略不计。那么，我能按时完成所有的任务吗？

容易想到，为了尽可能让所有任务都能按时完成，我最好是马不停蹄地工作，每完成一项任务以后，都不要休息片刻，立即开始着手另一项任务。这样一来，执行任务的先后顺序就成为了决定性的因素。或许在某种精心安排的任务执行顺序下，这些任务本来可以全部按时完成；但错误地采用了不恰当的任务执行顺序，有的任务就没法按时完成了。继续往下分析之前，大家不妨先凭借直觉想一想，如果你是我，你会怎么做呢？如果在你面前摆着一大堆要做的事情，每个事情都有一个截止时间，那么你会先做哪件事情呢？你一定会说，当然是先做最要紧的那件事情！

这种直觉是正确的。利用一些简单的数学推理方法，我们可以得出这样一个结论：最好的任务执行方案就是，按照截止时间从前往后的顺序依次进行，先做最要紧的事情，最后做最不要紧的事情，即使最要紧的事情花费的时间很少，即使最不要紧的事情需要花费很长的时间。

不妨假设在某种任务执行顺序当中，我们刚刚做完某个任务A，紧接着做了一个更要紧的任务B（换句话说，任务A的截止时间其实比任务B更晚）。那么如果原来的顺序就能让所有任务全部按时完成，交换A、B这两个任务以后，所有的任务仍然都能按时完成。为什么呢？首先，交换这两个任务，不会影响其他所有任务的开始时间和结束时间，它们和原来一样，照常可以按时完成；然后，把任务B放到任务A之前完成，会使得任务B比之前结束得更早，因而如果原来任务B就能按时完成，现在肯定也能按时完成。最危险的就是任务A了：它被安排到了任务B的后面，因而完成时间会比原来更晚，那它还能按时完成吗？当然可以！交换了两个任务的执行顺序后，现在任务A的结束时间就和原来任务B的结束时间一样了；但别忘了，任务A的截止时间比任务B的截止时间要晚，而原来任务B就能按时完成，现在任务A肯定也能按时完成。

因此，如果某种任务执行顺序的方案本来就能保证所有任务均可按时完成，但里面有两个相邻的任务，前面那个任务的截止时间反而更晚，那么我们就可以安全地交换这两个任务的执行先后顺序，所有的任务均可照常按时完成。如果新的任务执行顺序中还有这样的任务对，我们还能继续做交换。不断这样换呀换，换呀换，最终得到的结论就是，在所有可能的任务执行顺序中，只要有任何一种顺序是满足要求的，那么按照截止时间从前往后排列所得的顺序也一定满足要求；反之，如果这样都没法让所有任务全部按时完成，那么这些任务无论如何都没法全部按时完成了。

从8:00开始，依次执行上述6项任务，结果如何呢？买好投影仪已是8:30，好在它的截止时间是11:00；退掉车票后已是9:30，好在它的截止时间是12:00；写完代码后已是13:30，好在它的截止时间是15:00；写完稿子后已是15:30，好在它的截止时间是16:00；做好keynote之后已是18:30，好在它的截止时间是21:00；完成愚人节特别项目则要到22:30，好在它的截止时间是23:30。因此，我的任务可以全部按时完成！（事实上，那天的任务也确实全都按时完成了。）

让我们来看一个更复杂的问题。有一天，我和老婆去超市大采购。和往常一样，结完账之后，我们需要小心谨慎地规划把东西放进购物袋的顺序，防止东西被压坏。这并不是一件容易的事情，尤其是考虑到各个物体自身的重量和它能承受的重量之间并无必然联系。鸡蛋、牛奶非常重，但同时也很怕压；毛巾、卫生纸都很轻，但却能承受很大的压力。于是，我突然想到了这么一个问题：给定n个物体各自的重量和它能承受的最大重量，判断出能否把它们叠成一摞，使得所有的物体都不会被压坏（一个物体不会被压坏的意思就是，它上面的物体的总重小于等于自己能承受的最大重量），并且给出一种满足要求的叠放顺序（如果有的话）。

事实证明，这是一个非常有趣的问题——老婆听完这个问题后整日茶饭不思，晚上做梦都在念叨着自己构造的测试数据。这里，我们不妨给出一组数据供大家尝试。假设有A、B、C、D四个物体，其中：物体A的自重为1，最大承重为9；物体B的自重为5，最大承重为2；物体C的自重为2，最大承重为4；物体D的自重为3，最大承重为12。在这个例子中，安全的叠放方式是唯一的，你能找出来吗？

答案：C在最上面，其次是B，再次是A，最下面是D。注意，在这个最优方案中，最上面的物体既不是自身重量最小的，也不是承重极限最小的，而是自身重量与承重极限之和最小的。事实上，最优方案中的四个物体就是按照这个和的大小排列的！对于某种叠放方案中的某一个物体，不妨把它的最大载重减去实际载重的结果叫作它的安全系数。我们可以证明，这种按自身重量与载重能力之和排序的叠放策略可以让最危险的物体尽可能安全，也就是让最小的那个安全系数达到最大。如果此时所有物体的安全系数都是非负数，那么我们就相当于有了一种满足要求的叠放方案；如果此时仍然存在负的安全系数，那么我们就永远找不到让所有物体都安全的叠放方案了。

证明这一点的思路和刚才相同。假设在某种叠放方案中，有两个相邻的物体，上面那个物体的自身重量和最大载重分别为W1和P1，下面那个物体的自身重量和最大载重分别为W2和P2。再假设它俩之上的所有物体的重量之和是W，这是这两个物体都要承担的重量。如果W1+P1大于W2+P2，那么把这两个物体的位置交换一下，会发生什么事情呢？原先下面那个物体的安全系数为P2-W-W1，移到上面去之后安全系数变成了P2-W，这无疑使它更安全了。原先上面那个物体的安全系数为P1-W，移到下面后安全系数变成了P1-W-W2，这个值虽然减小了，但却仍然大于原先另一个物体的安全系数P2-W-W1（这里用到了W1+P1 > W2+P2的假设）。因此，交换两个物体之后，不但不会刷新安全系数的下限，相反有时还能向上改进它。

所以说，我们可以不断地把自身重量与载重能力之和更小的物体换到上面去，反正这不会让情况变得更糟。最终得到的最优方案，也就与我们前面给出的结论一致了。

最后，我们从易至难给出4个类似的问题，利用某种适当的贪心算法都能够得到最优解。大家不妨先从中挑选几个感兴趣的问题研究一下，再阅读后面的答案。

问题1. 在某个游戏里，有n个怪物正在围攻你。第i个怪物每秒钟会砍掉你ai滴血，杀死它需要花费ti秒的时间。为了让你掉的血最少，你应该按照什么顺序杀死这些怪物？

问题2. 一台计算机上面有m个单位的储存空间。现在我们手里有n个程序，其中第i个程序运行时需要占用Ri个单位的空间，储存结果则需要占用Oi个单位的空间（其中Oi一定小于Ri）。是否能够合理安排这些程序的运行顺序，使得所有程序都能顺利完成？如果可以，你需要给出一种方案。

问题3. 假设有n个藏宝地点。你已经知道了每个地点的寻宝成本ci和能挖到宝藏的概率pi。如何设计一个挖宝顺序，使得挖到第一个宝藏平均需要的总成本最少。这是由赫伯特·西蒙（Herbert Simon）和约瑟夫·卡登（Joseph Kadane）在1974年的一篇论文中提到的问题。

问题4. 假设有n个零件需要加工。每个零件都需要先在机器A上加工，再在机器B上加工。其中第i个零件在机器A上加工所需的时间为Ai，在机器B上加工所需的时间为Bi。注意，虽然两台机器可以并行运作，但每台机器每次只能加工一个零件。如何安排这n个零件的加工顺序，使得从第一个零件开始加工到最后一个零件完成加工所需要的时间最短。

下面是答案。这些答案的正确性证明都和之前的思路相仿，这里不再赘述。

问题1的答案：按照ai/ti的值从大到小杀怪。这非常符合我们的直觉：攻击力高的、容易被杀死的肯定应该先杀。正确性的证明也很容易。

问题2的答案：按照Ri-Oi从大到小的顺序执行任务。也就是说，谁运行完后会释放更多的空间，谁就应该优先处理。这种方案可以把空间消耗的最高峰降到最低。如果这样下来m个单位的空间仍然不够，那么可以肯定问题无解。

问题3的答案：按照ci/pi从小到大的顺序挖宝。这非常符合我们的直觉：寻宝成本小的、出宝概率大的肯定应该先挖。严格证明的思路和刚才差不多，但是中间会涉及不少数学运算。

问题4的答案：首先，Ai < Bi的一定排在Ai ≥ Bi的前面；如果两个零件的Ai都小于Bi，则Ai更小的排在前面；如果两个零件的Ai都大于等于Bi，那么Bi更大的排在前面。问题4是一个非常困难的问题，上面这个漂亮的算法是S·M·约翰逊（S. M. Johnson）于1954年给出的。这个算法背后的直觉就是，我们一定要减少机器B“等零件”的时间，最好让机器B前面的零件排上长队。因而，那些Ai小Bi大的先加工，那些Ai大Bi小的就后加工。不过，为什么刚才的方案一定是最优的，证明起来并不容易，需要考虑到很多不同的情况。这就留给感兴趣的读者了。