详情
“算法详解”系列图书共有4卷，本书是第3卷—贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、聚类、哈夫曼编码等，动态规划主要包括背包、序列对齐、最短路径、最佳搜索树等。本书的每一章均有小测验和章末习题，这将为读者的自我检查以及进一步学习提供方便。
本书作者提供丰富而实用的资源，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生、想要培养和训练算法思维、计算思维的IT专业人士，以及面试官和正在准备面试的应聘者阅读、参考。
书名：算法详解（卷3）——贪心算法和动态规划
ISBN：978-7-115-56334-7
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 ［美］蒂姆•拉夫加登（Tim Roughgarden）
译 徐 波
责任编辑 武晓燕
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
“算法详解”系列图书共有4卷，本书是第3卷——贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、聚类、哈夫曼编码等，动态规划主要包括背包、序列比对、最短路径、最佳搜索树等。本书的每一章均有小测验和章末习题，这将为读者的自我检查以及进一步学习提供方便。
本书作者提供丰富而实用的资源，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生、想要培养和训练算法思维、计算思维的IT专业人士，以及面试官和正在准备面试的应聘者阅读、参考。
本书是在我的在线算法课程基础之上编写的，是本系列图书（共4卷）的第3卷。这个在线算法课程从2012年起就定期发布，它建立于我在斯坦福大学讲授多年的本科课程的基础之上。本系列的前两卷并不是阅读卷3的先决要求，不过本卷的部分内容要求读者对“大O表示法”（卷1的第2章或卷2的附录介绍）、分治算法（卷1的第3章）和图（卷2的第1章）有所了解。
本书介绍两个基本的算法设计范例，并提供一些相关的案例。
贪心算法通过一系列短视和不可逆的决策序列来解决问题。对于很多问题而言，设计一种具有“炫目”速度的贪心算法是非常容易的。大多数贪心算法并不能保证其正确性，但我们将讨论一些重量级的应用，它们并不受这条规则的制约。贪心算法的例子包括调度问题、最优压缩以及图的最小生成树。
通过严谨的算法研究所获得的好处很少能够与精通动态规划所获得的好处相匹敌。某些设计范例需要大量的实践才能完善，但有无数的问题是无法通过其他任何更简单的方法解决的。我们的动态规划训练将涵盖这种编程范例的一些重要应用，包括背包问题、Needleman-Wunsch基因序列对齐算法、克努特（Knuth）的最优二叉搜索树算法以及贝尔曼·福特（Bellman·Ford）和弗洛伊德（Floyd·Warshall）的最短路径算法。
关于本书内容的更详细介绍，可以阅读每章的“本章要点”，它对每章的内容，特别是那些重要的概念进行了总结。“后记 算法设计工作指南”对贪心算法和动态规划算法应用于更大算法场景的方式进行了概括。
书中带“*”的章节是难度较高的章节。时间较为紧张的读者在第一遍阅读时可以跳过这些内容，这并不会影响本书阅读的连续性。
“算法详解”系列图书的卷1讨论了渐进性表示法（大O表示法以及相关表示法）、分治算法和主方法，随机化的QuickSort及其分析以及线性时间的选择算法。“算法详解”系列图书的卷2重点讨论了数据结构（堆、平衡搜索树、散列表、布隆过滤器）、图形基本单元（宽度和深度优先的搜索、连通性、最短路径）以及它们的应用（从去除重复到社交网络分析）。“算法详解”系列图书的卷4则介绍NP完整性及其对算法设计师的意义，还讨论了处理难解的计算问题的一些策略，包括对试探法和局部搜索的分析。
精通算法需要大量的时间和精力，那为什么要学习算法呢？
读者将学习一些“炫目”的、用于处理数据的高速子程序以及一些实用的数据结构，它们用于组织数据，我们可以将其直接部署到自己的程序中。理解和使用这些知识将扩展读者的编程知识范围并提高读者的编程技术水平。读者还将学习基本的算法设计范例，它们与许多不同领域的不同问题密切相关，并且可以作为预测算法性能的工具。这些“算法设计范例”可以帮助读者为自己遇到的问题设计新算法。
读者将获得大量对算法进行描述和推导的实践机会。通过数学分析，读者将对“算法详解”系列图书所涵盖的特定算法和数据结构产生深刻的理解。读者还将掌握一些广泛用于算法分析的实用数学技巧。
在学习算法之后，我们很难发现有什么地方没有它们的踪影。无论是坐电梯、观察鸟群，还是管理自己的投资组合，甚至是观察婴儿的认知，算法思维都如影随形。算法思维在计算机科学之外的领域，包括生物学、统计学和经济学等领域越来越实用。
研究算法就像观看计算机科学最近60年发展的精彩剪辑。当读者参加一场计算机科学界的鸡尾酒会，会上有人讲了一个关于Dijkstra算法的笑话时，你就不会感觉自己被排除在这个圈子之外了。在阅读本系列图书之后，读者将了解许多这方面的知识。
在过去的这些年里，有很多学生向我讲述了“算法详解”系列图书是怎样帮助他们在技术访谈中脱颖而出的。
“算法详解”系列图书只有一个目标：尽可能以读者容易接受的方式介绍算法的基础知识。读者可以把本书看成专家级算法教师的课程记录，教师以课程的形式传道解惑。
市面上还有一些非常优秀的、更为传统和全面的算法教材，它们都可以作为“算法详解”系列关于算法的其他细节、问题和主题的有益补充。我鼓励读者探索和寻找自己喜欢的其他教材。另外，还有一些教材的出发点有所不同，它们偏向于站在程序员的角度寻找一种特定编程语言的成熟算法实现。网络中存在大量免费的这类算法的实现代码。
“算法详解”系列图书以及作为其基础的在线课程的整体目标是尽可能扩展读者群体的范围。学习我的在线课程的人具有不同的年龄、背景、生活方式，有大量来自全世界各个角落的学生（包括高中生、大学生等）、软件工程师（包括现在的和未来的）、科学家和专业人员。
本书并不是讨论编程的，理想情况下读者至少应该熟悉一种标准编程语言（例如Java、Python、C、Scala、Haskell等）并掌握基本的编程技巧。作为一个立竿见影的试验，读者可以试着阅读第2.2节。如果读者觉得自己能够看懂，那么看懂本书的其他部分应该也是没有问题的。如果读者想要提高自己的编程技术水平，那么可以学习一些非常优秀的讲述基础编程的免费在线课程。
我们还会根据需要通过数学分析帮助读者理解算法为什么能够实现目标以及它是怎样实现目标的。埃里克·雷曼（Eric Lehman）、F.汤姆森·莱顿（F. Thomson Leighton）和艾伯特·R.迈耶（Albert R.Meyer）关于计算机科学的数学知识的免费课程是较为优秀的，可以帮助读者复习数学符号（例如Σ和∀）、数学证明的基础知识（归纳、悖论等）、离散概率等更多知识。
“算法详解”系列的在线课程当前运行于Coursera和Stanford Lagunita平台。另外，还有一些资源可以帮助读者根据自己的意愿提升对在线课程的体验。
● 视频。如果读者觉得相比阅读文字，更喜欢听和看，那么可以在视频网站中观看视频。这些视频涵盖了“算法详解”系列的所有主题。我希望它们能够激发读者学习算法的持续的热情。当然，它们并不能完全取代书。
● 小测验。读者怎么才能知道自己是否完全理解本书所讨论的概念呢？本书的小测验及其答案和详细解释就起到这个作用。当读者阅读这部分内容时，最好能够停下来认真思考，然后继续阅读接下来的内容。
● 章末习题。每章的末尾都有一些相对简单的习题，用于测试读者对该章内容的理解程度。另外，还有一些开放性的、难度更大的挑战题。本书并未包含章末习题的答案，但是读者可以通过本书的论坛（稍后提及）与作者以及其他读者交流。
● 编程题。许多章的最后有一个建议的编程项目，其目的是通过创建自己的算法工作程序，来帮助读者更深入地理解算法。读者可以在algorithmsilluminated网站上找到数据集、测试例以及它们的答案。
● 论坛。在线课程能够取得成功的一个重要原因是它们为参与者提供了互相帮助的机会，读者可以通过论坛讨论课程教材和调试程序。本系列图书的读者也有同样的机会，可以通过algorithmsilluminated网站参与活动。
如果没有过去几年里我的算法课程中数以千计的参与者的热情和渴望，“算法详解”系列图书就不可能面世。这些课程既包括斯坦福大学的课程，又包括在线平台的课程。我特别感谢那些为本书的早期草稿提供详细反馈的人：托尼娅·布拉斯特（Tonya Blust）、曹元（Yuan Cao）、卡洛斯·吉亚（Carlos Guia）、吉姆·休梅尔辛（Jim Humelsine）、弗拉基米尔·科克舍涅夫（Vladimir Kokshenev）、巴伊拉姆·库利耶夫（Bayram Kuliyev）和丹尼尔·津加罗（Daniel Zingaro）。
我非常希望得到读者的建议和修正意见，读者可通过上面所提到的网站与我进行交流。
蒂姆·拉夫加登
美国纽约
本书由异步社区出品，社区（https://www.epubit.com）为您提供后续服务。
作者、译者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“发表勘误”，输入错误信息，单击“提交勘误”按钮即可，如下图所示。本书的作者和编辑会对您提交的错误信息进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区投稿（直接访问www.epubit.com/contribute即可）。
如果您所在的学校、培训机构或企业想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接通过邮件发送给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、人工智能、测试、前端、网络技术等。
异步社区
微信服务号
算法设计及分析之优美，大多来自算法的基本设计原则以及在解决具体的计算问题时这些原则的具体体现之间的相互影响。在算法设计中，不存在能够解决所有计算问题的“万能钥匙”。但是，有一些基本的算法设计范例可以帮助我们解决许多不同应用领域的问题。学习这些算法设计范例以及它们著名的应用实例正是本系列图书的主要目标之一。
什么是“算法设计范例”呢？在本系列图书的卷1中，我们已经看到一个经典的例子，也就是分治算法范例。这个范例是按照下面的方式进行的。
（1）把输入划分为更小的子问题。
（2）递归地解决子问题。
（3）把子问题的解决方案组合为原问题的解决方案。
在本系列图书的卷1中，我们看到了这个算法范例的很多实例：MergeSort和QuickSort算法、Karatsuba的O(n1.59)时间级的两个n位整数相乘算法、Strassen的O(n2.71)时间级的两个n × n矩阵的相乘算法等。
本系列图书卷3的前半部分讨论贪心算法的设计范例。贪心算法的准确定义是什么？关于这个问题，可以说是“唾沫和墨汁横飞”。在这里我们不想横生枝节，因此只讨论它的一个非正式定义。[1]
[1] 如果想探究贪心算法的正式定义，可以从Allan Borodin、Morten N.Nielsen和Charles Rackoff的论文（Incremental）Priority Algorithm[（增量的）优先级算法，Algorithmica，2003]入手。
通过一个“短视”的决策序列，以迭代的方式创建一个解决方案，并期望一切最终都能按照这种方案得到解决。
领会贪心算法精神的较好方式是通过实例。我们接下来将观察一些实例。[2]
[2] 本系列图书卷2的读者已经看到过一种贪心算法，即Dijkstra的最短路径算法。这种算法采用迭代的方式计算从一个起始顶点到图中其他每个顶点的最短路径长度。在每次迭代中，这种算法采用不可反悔和短视的方式提交到达一个额外顶点的最短路径长度，通常不会重新回到原先的决策。在仅包含非负长度边的图中，这种算法不会遇到问题，所有估测的最短路径长度都是正确的。
在我们的例子中，有一些特性值得关注（读者在钻研了一个或多个例子之后可能会重新阅读本节，因此我尽量说得不那么抽象）。首先，对于许多问题，令人吃惊的是找到一种甚至多种看上去似乎行之有效的贪心算法很容易。这虽是优点但也暗藏陷阱。当我们受困于某个问题时，贪心算法很可能就是我们脱困的“良方”。但是，我们又很难评估哪种贪心算法是最为适合的。其次，贪心算法的运行时间分析常常非常简单。例如，许多贪心算法的运行时间可以归纳为排序复杂度加上一些线性时间的额外处理，此时一种良好的贪心算法实现的运行时间可以达到O(nlogn)，其中n是需要进行排序的对象数量。[3]（大O表示法忽略了常数项以及仅是常数因子不同的对数函数，因此不需要指定对数的底。）最后，我们常常很难确定一种推荐的贪心算法对于每种可能的输入是否都能返回正确的输出。我们所害怕的情况是算法中的某些不可后悔的短视决策可能会是一直萦绕在我们心头的“阴影”，当我们明确它是个糟糕思路的时候往往已是“事后诸葛”。而且，即使一种贪心算法是正确的，要想证明这一点也是非常困难的。[4]
[3] 例如，MergeSort（参见卷1的第1章）和HeapSort（参见卷2的第4章）是两种O(nlogn)时间级的排序算法。另外，随机化的QuickSort（参见卷1的第5章）的平均运行时间也是O(nlogn)。
[4] 熟读本系列图书卷1的读者应该知道这3个特性与分治算法范例正好形成鲜明的对照。为一个问题设计出一种良好的分治算法常常是比较困难的。但是一旦想到，就会产生很明确的感觉“就是它了！”，因为我们知道解决问题已经不在话下。由于不断增加的子问题数量和每个子问题不断缩减的工作量之间的拉锯战，因此分治算法的运行时间分析也是非常困难的（卷1的第4章也讨论过这个话题）。分治算法的正确性证明是非常简单明了的。
贪心算法范例的优点和缺点
（1）容易想出一种或多种贪心算法。
（2）容易分析运行时间。
（3）很难证明它的正确性。
贪心算法的正确性很难证明的其中一个原因是这类算法有很多是不正确的，这意味着在有些输入的情况下这类算法无法产生符合预期的输出。如果我们只能记住贪心算法的一个特点，那就是它了。
警告
大多数贪心算法并不总是正确的。
我们很难接受自己所设计的巧妙贪心算法并不总是正确的。我们在内心深处坚信，自己所设计的自然贪心算法总能够正确地解决问题。但事与愿违，这种想法并没有事实根据。[5]
[5] 并不总是正确的贪心算法仍然可以启发我们快速找到问题的解决方案，这是我们在卷 4 将要讨论的观点。
说清楚这个事情之后我就问心无愧了，下面我们就观察一些可以通过设计严谨的贪心算法正确解决问题的精选例子。
我们的第1个案例与调度有关，它的目标是对一个或多个共享资源的任务进行调度，实现一些目标的优化。例如，共享资源可能是计算机处理器（其任务对应于操作系统中的作业）、教室（其任务对应于授课）或日历（其任务对应于会议）。
在调度中，需要完成的任务通常被称为作业，作业可能具有不同的特性。假设每个作业j具有已知的长度
，表示处理这个作业所需要的时间（例如，一节课或一个会议的时长）。另外，每个作业具有权重wj，权重越高，作业的优先级也就越高。
调度指定作业的处理顺序。在一个由n个作业所组成的问题中，共有n! = n×(n−1)×(n−2)...2×1种不同的调度方式。这个数量是极为惊人的，我们应该选择哪一种调度方式呢？
我们需要定义一个目标函数，为每种调度方式评分，并对我们的需求进行量化。首先，我们来看一个初步的定义——完成时间。
在一次调度σ中，作业j的完成时间Cj(σ)是σ中j之前的作业长度之和加上j本身的长度。
换句话说，在一次调度中，一个作业的完成时间就是这个作业处理完成时总共所经过的时间。
小测验1.1
考虑一个问题，有3个作业，它们的长度分别是
、
、
并假设它们按照这个顺序进行调度（作业1首先执行）。在这次调度中，3个作业的完成时间分别是什么（这个问题与作业的权重无关，因此我们并没有指定权重）？
（a）1、2和3
（b）3、5和6
（c）1、3和6
（d）1、4和6
（关于正确答案和详细解释，参见第1.2.4节。）
什么才是良好的调度呢？我们希望作业的完成时间尽可能短，但作业之间的权衡是不可避免的。在任何调度中，较早被调度的作业具有较短的完成时间，而较晚被调度的作业具有较长的完成时间。
在作业之间进行权衡的一种方式是尽量减少加权完成时间之和。在数学中，这个目标函数可以定义为：
（1.1）
其中最小化是针对所有n!种可能出现的调度σ，Cj(σ)表示作业j在调度σ中的完成时间。它的目标是尽可能地减少作业的加权平均完成时间，而平均权重与wj成正比。
例如，考虑小测验1.1中的3个作业，并假设它们的权重w1 = 3、w2 = 2、w3 = 1。如果我们把第1个作业放在最前，第2个作业放在其次，第3个作业放在最后，那么加权完成时间之和是
通过检查3！= 6种可能的调度，我们可以证实这种调度方式确实最大限度地减少了加权完成时间之和。那么，假设输入是一组任意长度和权重的作业，我们怎样才能得到这个问题的通用解决方案呢？
问题：最大限度地减少加权完成时间之和
输入：一组n个作业，它们具有正的长度
,
,...,
和正的权重
,
,...,
。
输出：一个作业序列，它具有最小的加权完成时间之和即式（1.1）。
由于总共有n!种不同的调度方式，因此对于作业数量较多的问题采用穷举法计算最佳调度方式是完全不实用的。我们需要一种更为智能的算法。[6]
[6] 例如，当n = 10时，n ! > 3.6×107。当n = 20时，n ! > 2.4×1018。当n≥60时，n !甚至大于宇宙中的原子估计数量。因此，计算机技术是没有办法把这种穷举法作为一种实用算法的。
正确答案：（c）。我们可以通过把作业上下堆放在一起形象地表示调度，时间是从下向上增长的（见图1.1）。作业的完成时间就是它的顶边对应的时间。对于第1个作业，它的完成时间就是它的长度，也就是1。第2个作业必须等待第1个作业完成，因此它的完成时间就是前两个作业的长度之和，也就是3。第3个作业在时间3之前不会启动，因此它需要额外的3个时间单位才能完成，它的完成时间是6。
图1.1 3个作业的完成时间分别是1、3和6
贪心算法看上去适用于寻找具有最小加权完成时间之和的作业调度问题。它的输出具有一种迭代式的结构，作业是一个接一个地进行处理的。为什么不使用一种贪心算法以迭代的方式决定下一个作业应该是谁呢？
在我们的计划中，首先是解决基本问题的两种特殊情况。这两种特殊情况的解决方案提示基本情况下贪心算法会是什么样子的。然后，我们把范围缩小到一种候选算法，并证明这种候选算法能够正确地解决问题。知道这种算法生成的过程要比记住算法本身更为重要。它是我们在自己的应用程序中可以使用的可重复过程。
我们首先积极地假设实际已经存在一种正确的贪心算法，它可以解决寻找最小加权完成时间之和的问题。这种算法会是什么样的呢？作为初始情况，如果所有的作业都具有相同的长度（但可能具有不同的权重）应该怎么调度呢？如果它们具有相同的权重（但可能具有不同的长度）又该怎么调度呢？
小测验1.2
（1）如果所有作业的长度都是相同的，我们应该把权重较小的作业还是权重较大的作业放在前面？
（2）如果所有作业的权重都是相同的，我们应该把长度较长的作业还是长度较短的作业放在前面？
（a）较大/较短
（b）较小/较短
（c）较大/较长
（d）较小/较长
（关于正确答案和详细解释，参见第1.3.3节。）
通常情况下，不同的作业可能具有不同的权重和长度。如果我们的两个规则（优先选择更短的作业和优先选择权重更大的作业）正好都适用于一对作业，我们立即就能知道应该把哪个作业调度在前面（长度更短或权重更大的那个作业）。但是，如果这两个规则出现了冲突又该怎么办呢？如果其中一个作业的长度更短而另一个作业的权重更大，我们又该怎么选择呢？
最简单的贪心算法的工作方式是怎么样的？每个作业具有2个参数，这种算法必须综合考虑这两个参数。最佳场景是设计出一个公式，综合每个作业的长度和权重评定一个分值，这样按照从高到低的分值顺序对作业进行调度以保证能够产生最小的加权完成时间之和。如果存在这样的公式，那么前面的两种特殊情况提示必定具有2个属性：如果长度固定不变，则权重越大分值越高；如果权重固定不变，则长度越长分值越低（记住，分值越高越好）。开展一会儿头脑风暴，想出一些同时满足这两个属性的公式。
也许最为简单的随权重增大而增大并随长度增加而减小的公式是取两者之差。
作业j的分值的第1个提议：
。
这个公式所产生的分值可能是负的，但并不会妨碍作业的分值从高到低排列。
其他可供选择的方案还有很多。例如，这两个参数之比也是一种候选方案。
作业j的分值的第2个提议：
。
这两个不同的公式产生了两种不同的贪心算法。
（1）GreedyDiff。按照分值的降序对作业进行调度（若两个作业分值相等，则任意调度）。
（2）GreedyRatio。按照分值的降序对作业进行调度（若两个作业分值相等，则任意调度）。
因此，我们的第1个案例已经形象地描述了贪心算法设计范例的第1个特性（第1.1.2节）：为一个问题提出多种具有竞争力的贪心算法常常是非常容易的。
那么，如果存在两种算法，哪个才是正确的呢？排除其中一种算法的一种简单方法是找出一个这两种算法输出不同调度方案的例子，使它们具有不同的目标函数值。不管哪种算法在这个例子中的表现较差，我们都可以认为它并不总是最优的。
这两种算法在两种特殊情况（具有相同权重或相同长度的作业）下都能正确地工作，排除其中一种算法的一种简单方法是通过一个具有两个作业的问题实例，这两个作业具有不同的权重和长度，使这两种算法正好按照相反的顺序进行调度。也就是说，我们寻找一个例子，按分值之差进行调度和按分值之比进行调度的顺序正好相反。一个简单的例子如下。
| 作业1 |
作业2 |
|
| 长度 |
|
|
| 权重 |
w1=3 |
w2 = 1 |
第1个作业具有较大的分值比（
），但它的分值差较小（
）。因此，GreedyDiff算法把第2个作业调度在前面，而GreedyRatio则与之相反。
小测验1.3
GreedyDiff和GreedyRatio算法所输出的加权完成时间之和分别是什么？
（a）22和23
（b）23和22
（c）17和17
（d）17和11
（关于正确答案和详细解释，参见第1.3.3节。）
通过排除GreedyDiff算法，我们已经取得一些进展。但是，小测验1.3的结果并没有证明GreedyRatio算法总是最优的。我们只知道，GreedyDiff算法在某种情况下所输出的是一种次优的调度。对于不存在正确性证明的算法，我们应该总是对它保持怀疑，即使它在某些简单的例子中能够正确地完成任务。对于贪心算法，我们要保持加倍的警惕。
在这个例子中，GreedyRatio算法事实上能够保证产生最小的加权完成时间之和。
定理1.1（GreedyRatio的正确性） 对于每组拥有正的权重w1,w2,...,wn和正的长度,,...,的作业，GreedyRatio算法所实现的调度方式能够产生最小的加权时间之和。
这个定理并非显而易见，如果我不提供证明，可能无法让读者信服。这正好与贪心算法设计范例的第3个特性（第1.1.2节）保持一致，这个定理的证明将作为整个第1.4节的内容。
关于辅助结论、定理等术语
在数学著作中，重要的技术性陈述被称为定理。辅助结论是一种帮助证明定理的技术性陈述（就像一个子程序帮助实现一个更大的程序一样）。推论是一种从已经被证明的结果中引导产生的陈述，例如一个定理的一种特殊情况。对于那些本身并不是特别重要的独立的技术性陈述，我们将使用命题这个术语。
贪心算法范例的第2个特性就是容易进行运行时间分析（第1.1.2节），显然也符合当前这个例子。GreedyRatio算法所做的工作就是根据比例对作业进行排序，它需要O(n log n)的时间复杂度，其中n是输入中作业的数量（参见脚注3）。
正确答案：（a）。首先假设所有n个作业都具有相同的长度，例如1。这样，每个调度都有一组完全相同的完成时间：{1, 2, 3, …,n}。唯一的问题是哪个作业对应于哪个完成时间。作业权重的含义提示具有更大权重的作业应该具有更少的完成时间，事实上也确实如此。例如，我们不希望把权重为 10 的作业调度在第3个位置（完成时间为3），把权重为20的作业调度在第5个位置（完成时间为 5）。我们更想交换这两个作业的位置，这样就可以把加权完成时间之和减少20（读者可以验证）。
在第2种情况下，所有的作业具有相同的权重，此时有点微妙。此时，我们优先调度长度较短的作业。例如，考虑两个长度分别为1和2的单位权重的作业。如果我们首先调度长度更短的那个作业，那么完成时间分别为1和3，总共为4。如果按照相反的顺序进行调度，完成时间分别是2和3，总共是较差的5。一般而言，首先调度的作业的完成时间会加到所有作业的完成时间中，因为所有作业都必须等待第1个作业的完成。在其他条件都相同的情况下，优先调度长度最短的作业可以最大限度地减少负面影响。第2个执行的作业的完成时间会加到除第1个作业之外的所有作业的完成时间中，因此具有次短长度的作业应该被调度为第2个执行，接下来以此类推。
正确答案：（b）。GreedyDiff算法把第2个作业调度为率先执行。这个作业的完成时间是C2 == 2，而另一个作业的完成时间是C1 =
= 7。因此，这两个作业的加权完成时间之和是
w1 · C1 + w2 · C2 = 3 × 7 + 1 × 2 = 23
GreedyRatio算法把第1个作业调度为率先执行，使这两个作业的完成时间分别是C1 = = 5和C2 =
= 7，从而加权完成时间之和是
3 × 5 + 1 × 7 = 22
我们可以得出结论，在这个例子中，GreedyDiff算法无法给出最优的调度方案，因此它并不总是正确的。
分治算法通常具有更加形式化的正确性证明，由简单明了的归纳步骤组成。贪心算法则不同，它的正确性证明更像是艺术而不是科学。在某种程度上，我们可以在贪心算法的证明中反复看到它的几个特性，我们将在证明过程中对它们进行强调。
定理1.1的证明包含了其中一个特性的一个生动例子：交换参数法。它的关键思路是每种可行的解决方案都可以通过修改使之更接近贪心算法的输出来得到改进。我们在本节中将看到两个变型。在第1个变型中，我们将采用反证法，并使用一种交换参数法展示一个“太过美好难以成真”的解决方案。在第2个变型中，我们将使用一种交换参数法来说明每种可行的解决方案都可以迭代地“挤压”到贪心算法的输出中，在此过程中会一直对解决方案进行改进。[7]
[7] 交换参数法仅仅是证明贪心算法正确性的诸多方法中的一种。例如，在本系列图书卷2的第3章，Dijkstra算法的正确性证明使用了数学归纳法而不是交换参数法。数学归纳法和交换参数法在哈夫曼的贪婪编码算法（第2章）以及Prim和Kruskal的最小生成树（Minimum Spanning Tree，MST）算法（第3章）的正确性证明中都扮演了重要的角色。
我们继续证明定理1.1。对于一组固定的作业，其权重分别是正的w1,w2,...,wn，其长度分别是正的,,...,。我们必须证明GreedyRatio算法所产生的调度方案具有最小的加权完成时间之和。我们首先从两个前提条件开始。
（1）作业的索引顺序是按照权重长度比率的非升序排列的，即
（1.2）
（2）不存在相同的比率：当i ≠ j时，
。
第1个前提条件是为了不失去普遍性，它仅仅是一个“君子协定”，用于最大限度地减少记法上的负担。在输入中对作业进行重新排序对需要解决的问题并没有什么影响。因此，我们总是可以对作业进行重新排序和重新索引，使式（1.2）得以成立。第2个前提条件对输入施加了一个重要的限制，我们将在第1.4.4节通过一些额外的工作消除这个前提条件。总之，这两个前提条件提示作业将按权重长度比率的大小严格降序排列。
我们的高层计划采用反证法。记住，在这种类型的证明中，我们先提出与需要证明的命题相反的假设，然后在这个假设的基础上展开一系列逻辑正确的步骤并最终得出一个明显错误的结论。这就说明之前的那个假设是错误的，从而证明了我们原先需要证明的命题。
首先，我们假设GreedyRatio算法为一组特定的作业所产生的调度方案σ并不是最优的。这样一来，这些作业就存在一种最优的调度方案σ*，它具有严格最小的加权完成时间之和。我们的灵感就是使用σ和σ*之间的差明确地创建一种比σ*更好的调度方案，而这恰好与σ*是最优调度方案的假设相悖。
为了完成这个反证法，我们假设GreedyRatio算法产生的调度方案是σ，并且还存在一个更优的调度方案σ*，后者具有严格更小的加权完成时间之和。根据第1个前提条件，贪婪调度方案σ按照索引顺序对作业进行调度（首先是作业1，其次是作业2，一直到作业n），如图1.2所示。
图1.2 在贪婪调度方案σ中，作业是按照非升序的权重长度比率调度的
在贪婪调度方案中，作业的索引是从下到上不断增大的。在其他任何调度方式中，情况均非如此。
精确起见，我们把调度方案中的相邻逆序对（consecutive inversion）定义为一对作业i和j，满足i > j并且作业i恰好是在作业j之前处理的。例如，在图1.2中，如果作业2和作业3是按照相反的顺序处理的，它们就构成一个相邻逆序对（i = 3且j = 2）。
辅助结论1.1（非贪婪的调度中存在逆序对） 与贪婪调度方案 σ 不同的每种调度方案
至少存在一个相邻逆序对。
证明：我们采用反证法。[8]如果不存在相邻逆序对，则每个作业的索引至少比它前面的那个作业大1。由于一共存在n个作业，并且最大可能出现的索引是n，因此两个连续的作业之间索引的差值不可能达到2或更大。这意味着与贪心算法所计算的调度方案相同。证毕。
[8] “如果A为真，则B为真”这个命题在逻辑上相等的逆反命题是“如果B不为真，则A不为真”。例如，辅助结论1.1的逆反命题是：如果
不存在相邻逆序对，则就与贪婪调度方案σ相同。
回到定理1.1的证明，我们假设一组特定的作业存在最优的调度方案σ*，它相比贪心算法所产生的调度方案σ具有严格更小的加权完成时间之和。由于σ* ≠ σ，把辅助结论1.1应用于σ*，因此σ*存在相邻的作业i、j满足i > j（见图1.3（a））。我们应该如何使用这个事实来说明存在另一个比σ*更优秀的调度方案
，从而完成这个反证法呢？
图1.3 通过交换一对相邻逆序的作业（i > j），根据假设的最优调度σ∗获得新的调度σ′
关键的思路就是执行交换。我们定义一个新的调度方案，它与σ*基本相同，唯一的区别是作业i和j按照相反的顺序处理，作业j现在正好在i之前被处理。i和j之前的作业（图1.3中的“作业”）在σ*和σ′中是相同的。类似地，在i和j之后的作业（图1.3中的“更多作业”）在σ*和σ′中也是相同的。
图1.3所描述的交换会产生什么影响呢？
小测验1.4
图1.3的交换对下列作业的完成时间的影响：①除i和j之外的其他作业；②作业i；③作业j。
（a）①信息不足无法回答；②增加；③减少
（b）①信息不足无法回答；②减少；③增加
（c）①没有影响；②增加；③减少
（d）①没有影响；②减少；③增加
（关于正确答案和详细解释，参见第1.4.5节。）
正确地解答小测验 1.4 之后，我们就处于完成证明的极佳位置。交换一对相邻逆序的作业的成本是作业i的完成时间Ci增加了作业j的长度，目标函数（1.1）的增量是
。交换所得到的收益是作业j的完成时间Cj减少了作业i的长度
，目标函数（1.1）的减量是
。
综合成本和收益，其结果是
（1.3）
现在我们可以得出结论，σ*在i > j的情况下是按照“错误的顺序”对i和j进行调度的。前文的两个前提条件提示作业是按照权重长度比率的严格降序进行索引的，因此
消除分母之后，这个公式可以转换为
由于执行交换的收益超过了成本，因此式（1.3）告诉我们：σ′的目标函数值小于σ*的目标函数值。
但这显然是“胡说八道”，因为σ*已经被假设为最优的调度方案，其具有最小的加权完成时间之和！这样，我们就看到了悖论的出现，从而完成定理1.1在所有的作业都具有不同的权重长度比率的情况下的证明。
再努力一些，我们就可以证明GreedyRation算法（定理1.1）的正确性了，即使不同作业的权重长度比率存在平局（我们仍将保留第1个前提条件，即作业按照权重长度比率的非升序索引，因为它不会影响这个定理的普遍性）。完成这个更具普遍性的正确性证明的要点就是对前文的交换参数法进行一些修改，采用直接处理而不是采用反证法。
我们将重复利用前文的大量工作，但采用的高层计划有所变化。和前文一样，假设σ = 1,2,...,n表示GreedyRation算法所计算的调度方案。考虑任意一种有竞争力的调度方案σ*，它可能是最优的也可能不是。我们将通过一系列的作业交换直接说明这一点，也就是σ的加权完成时间之和不大于σ*的加权完成时间之和。如果对于每个σ*都能证明这一点，我们就能推断出σ事实上是最优的调度方案。
更详细地说，假设σ*≠ σ（如果σ* = σ就不需要做什么了）。根据辅助结论1.1，σ*中存在相邻逆序对，也就是存在两个作业i和j，且i > j但j是紧随i之后被调度的。通过在调度方案σ*中交换i和j的位置，就可以得到调度方案σ′。在式（1.3）的一种变型中，这次交换的成本和收益分别是和。由于i > j并且所有的作业是根据权重长度比率的非升序索引的，因此
从而可以证明
（1.4）
换句话说，这样的交换并不会增大加权完成时间之和，时间之和可能会减小，也可能保持不变。[9]
[9] 在这种情况下我们并不能直接通过反证法来证明，当σ∗是一种最优的调度方案时，σ′也可能是另一种具有相同效果的不同最优调度方案。
我们是不是已经取得一些进展？
小测验1.5
调度方案中的逆序对是指一对作业k和m，其中k < m并且m是在k之前处理的（作业k和m并不一定是相邻的，在m之后和k之前可能还有一些其他作业）。假设σ1这个调度方案具有一个相邻逆序对i, j（i > j），通过反转i和j的顺序可以得到σ2这个调度方案。σ2中的相邻逆序对数量与σ1相比是怎么样的呢？
（a）σ2中的相邻逆序对要比σ1少1个
（b）σ2具有与σ1相同的相邻逆序对
（c）σ2中的相邻逆序对要比σ1多1个
（d）以上答案均不正确
（关于正确答案和详细解释，参见第1.4.5节。）
为了完成证明，取任意一种有竞争力的调度方案 σ*，并反复交换作业以消除相邻逆序对。[10]由于在每次交换之后相邻逆序对的数量会减少（小测验1.5），因此这个过程最终会结束。根据辅助结论1.1，它结束时的状态就是贪婪调度方案σ。在整个过程中，目标函数的值只会减小（根据式（1.4）），因此σ至少与σ*同样优秀。对于σ*的每种选择，这个结论都是成立的，因此σ确实是最优调度方案。证毕。
[10] 熟悉冒泡排序（BubbleSort）算法的读者可能会在这里意识到它的存在，尽管只是在分析中而不是在算法中！
正确答案：（c）。首先，除i和j之外的其他作业k不会因为i和j的交换而受到影响。对于σ*中在i和j之前被处理的作业k，情况尤其明显（图1.3中的“作业”）。由于交换发生在k完成之后，因此它对k的完成时间（在k完成时所经历的总时间）并没有影响。对于σ*中在i和j之后被处理的作业k（图1.3中的“更多作业”），在k之前所完成的作业集合在σ*和σ′中是相同的。一个作业的完成时间只取决于在它之前的这组作业（与它们的顺序无关），因此作业k在这两种调度方案中的完成时间是相同的。
至于作业i，它的完成时间在σ′中增加了。它除了必须等待与此前相同的作业之外还必须等待作业j完成，因此它的完成时间增加了。类似地，作业j除了等待与以前相同的作业集合之外，它在σ′中不再等待作业i的完成。因此，j的完成时间减少了。
正确答案：（a）。如果{k,m} = {i,j}，则k和m在σ1中形成一个逆序对但在σ2中并没有（因为执行交换之后消除了逆序）。如果k或m至少有一个与i和j都不同，那么它们在这两个调度方案中要么都出现在i和j之前，要么都出现在i和j之后，i和j的交换不会对k和m的相对顺序产生影响（见图1.4）。我们可以得出结论，除了i和j这个逆序对之外，σ2和σ1中的其他逆序情况完全相同。
图1.4 交换一个相邻逆序对的作业把逆序对的数量减少了1。（b）中的5对作业在
两种调度方案中具有相同的相对顺序
● 贪心算法通过迭代的方式构建解决方案。在这个过程中，它本着“船到桥头自然直”的态度，采取了一系列只顾眼前的短视决策。
● 为一个问题提出一种或多种贪心算法并分析它们的运行时间常常是比较容易的。
● 大多数贪心算法并不总是正确的。
● 即使一种贪心算法总是正确的，要想证明这一点也是非常困难的。
● 对于具有给定长度和权重的作业，采取贪婪的方式根据权重长度比率从高到低对它们进行排列能够最大限度地减小加权完成时间之和。
● 在贪心算法的正确性证明中，交换参数法是常用的技巧之一。它的思路是证明每种可行的解决方案都可以通过使之更靠近贪心算法来得到改进。
问题1.1 假设有n个输入作业，每个作业具有长度和最后期限dj。在调度方案σ中把作业j的延迟λj(σ)定义为作业的完成时间和最后期限之差，即Cj(σ) – dj。如果Cj(σ)≤dj则定义为0（参见前文对作业的完成时间的定义）。这个问题的目标是最大限度地减少最大延迟
。
下面哪种贪心算法所产生的调度方案能够最大限度地减少最大延迟？可以假设作业之间不存在平局的情况。
（a）按照最后期限dj的升序对作业进行调度
（b）按照处理时间pj的升序对作业进行调度
（c）按照djpj的升序对作业进行调度
（d）上述答案均不正确
问题 1.2（H） 继续问题 1.1，考虑把目标换成最大限度地减少总延迟
。
下面哪种贪心算法所产生的调度方案能够最大限度地减少总延迟？可以假设作业之间不存在平局的情况。
（a）按照最后期限dj的升序对作业进行调度
（b）按照处理时间pj的升序对作业进行调度
（c）按照djpj的升序对作业进行调度
（d）上述答案均不正确
问题1.3（H） 假设有n个输入作业，每个作业具有开始时间sj和完成时间tj。如果两个作业在时间上出现了重叠（其中一个作业是在另一个作业的开始时间和完成时间之间开始的），它们就存在冲突。在本问题中，我们的目标是选择这些作业的一个最大无冲突子集（例如，假设3个作业的起止时间分别是[0, 3]、[2, 5]和[4, 7]，最优的解决方案就是第1个和第3个作业）。我们的计划是设计一种迭代式的贪心算法，在每次迭代时不可反悔地在目前为止的解决方案中添加一个新作业j，并在以后的处理中不再考虑与j冲突的所有作业。
下面哪种贪心算法能够保证生成一种最优解决方案？可以假设各个作业之间不存在平局的情况。
（a）在每次迭代时，选择剩余作业中具有最早完成时间的
（b）在每次迭代时，选择剩余作业中具有最早开始时间的
（c）在每次迭代时，选择剩余作业中需要时间最少的（具有最小的tj –sj值）
（d）在每次迭代时，选择剩余作业中与其他作业冲突数量最少的
问题 1.4 用自己最喜欢的编程语言实现第1.3节的GreedyDiff和GreedyRatio算法，实现最小的加权完成时间之和。用这两个算法解决相同的问题。GreedyRatio算法所产生的调度方案要比GreedyDiff算法所产生的调度方案优秀多少呢？（关于测试用例和挑战数据集，参见algorithmsilluminated网站。）
