英语原文共 94 页，剩余内容已隐藏，支付完成后下载完整资料
附录 译文
贪心算法
在华尔街，20世纪80年代的偶像电影，迈克尔.道格拉斯走到了充满股民的大厅前面，宣布：“贪心......是好事，贪心是成功的”。在这一章，当我们在算法设计中从正反两面研究目光短浅的贪心法时，要有一种多得多的全方位的理解。的确。我们的目的是处理大量不同的计算问题，在处理过程中出现以下的问题：贪心法好不好 ？贪心法有效吗？
如果要精确的定义的贪心算法的含义也不是不可能的，那样很难。一个算法是贪心的，如果它是通过一些小的步骤来建立一个解，在每一步根据局部情况选择一个决定使得某些主要的指标能得到优化。对于同一个问题常常可以设计许多不同的贪心算法，每个算法局部地、增量地优化在求解过程中的某些不同的量。
当一个贪心算法优化地成功求解了一个不平凡的问题时，它通常隐含了某些有趣的、与问题本身结构有关的有用的东西；存在一个局部判断规则可以用来构造问题的最优解。正如后面11章我们将看到的，问题同样如此，即使一个贪心算法不能得到精确的最优解，它也可以产生一个保证接近于最优解的解。我们在本章涉及的有这样几类问题。对于几乎任何问题都容易发明一个贪心算法；但是找到适合于它们工作的情况，并且证明它们做得很好是一个有趣的挑战。
本章的的前两节逐步阐的明两个基本的方法来证明一个贪心算法对一个问题提供一个最优解。第一个方法可以看作是建立贪心算法领先的概念。这里的含义是如果一个人以一步接一步的方式测量贪心算法的进展时，他会看到在每一步都比其他算法好；从而证明产生了一个最优解。第二个方法被称为交换论证，它是更一般化：考虑对这个问题的任何可能的解，逐渐把它转换层贪心算法找到的解且不损害它的质量。从而它也证明了贪心法一定找到了一个至少与其他解一样好的解。
在引入这两种风格的分析以后，我们将专注于贪心算法的几个最著名的应用，途中的最短路径，最小生成树问题，以及为实现数据压缩构造Huffman码。它们每一个都为我们的分析技术提供了好例子。我们也探索在最小的生成树与长期研究的聚类问题之间的有趣关系。最后我们考虑一个更复杂的应用，最小费用有向树问题，它将把什么是贪心算法的概念进一步加以推广。
4.1 区间调度：贪心算法领先
让我们回顾一下区间调度问题，这是第一章考虑的五个典型问题的第一个问题。我们有一组需求｛1,2,...,n｝；第i个需求与一个始于且止于的时间区间相对应（注意我们的符号与1.2节的符号稍有改变，那里使用而不是且使用而不是，记号的改变将使得在证明中更容易叙述事情）。如果没有两个需求在时间上重叠，我们就说需求的子集是相容的，我们的目标是接受一个最大的相容子集，最大的相容子集叫做最有子集。
4.1.1 设计贪心算法
试用区间调度问题，可以使我们关于贪心算法的讨论更加具体。区间调度问题的贪心算法中的基本思想就是使用一个简单的规则来选择第一个需求。一旦一个需求被接受，我们拒绝所有与不相容的需求然后选择下一个被接受的需求，且再次拒绝所有与不相容的需求，按这种方式继续下去知道我们走完了所有需求。在设计一个好的贪心算法中的挑战是决定用哪个简单的规则来选择——对这个问题存在许多自然的但给不出好的解的规则。
让我们设想某些最自然的规则并且看看它们效果怎么样。
● 最明显的规则可能总是选最早的开始的有效需求——即一个具有最小开始时间的的需求。按这种方式能尽早地开始试用我们的资源。
这个方法不能得到最优解。如果最早需求i是关于一个很长时间区间的，那么接受了需求i，我们可能要拒绝一大批对于较短时间区间的需求。由于我们的目标是满足尽可能多的需求，我们将以一个不是最理想的解结束。在真的坏的情况——比如说，当结束时间是所有需求中最大的——所接受的需求i将使我们的资源整个时间都被它占用。在这种情况下 我们的贪心法只能接受一个需求，而最优解可能接受许多需求。这样一个解给在图4.1（a）。
● 这可能建议我们应该从接受最小时间区间的需求开始——即—尽可能小的需求。结果是，某种情况下这是比前一个规则好一点的规则，但是它仍旧可能产生一个不是最理想的调度。例如，在图4.1（b），在中间接受一个最短的区间将阻止我们接受其他构成最优解的两个区间。
● 在前一个贪心规则中，我们的问题是第二个需求与第一和第三需求都竞争 ——即接受这个需求使得我们拒绝了其他两个需求。我们可以基于下面的思想来设计一个贪心算法：对每个需求，我们计算其他不相容的需求个数，并且接受有着最少不相容个数的需求（换句话说我们选择具有最少“冲突”的区间）。这个贪心选择在前一个例子将得到最优解。
图4.1 区间调度的某些实例，其中自然的贪心算法找不到最优解.在（a）中
选择最早开始的区间没有用；在（b）中选择最短的区间没有用；在
（c）中选择冲突最少的区间也没有用
事实上，为设计针对这个规则的一个坏的例子有一点难度，但是可以做到，并且我们已经在图4.1（c）中画了一个例子，在这里例子中唯一的最优解是接受在最上面一行的4个需求，而贪心法在这里却建议接受第二行中间的需求，因此只保证了一个大小不超过3的解。
一个导致最优解的贪心规则是基于第四个思想，我们应该接受最早结束的需求，即f(i)尽可能的小的需求i为第一个需求。这也是相当自然的想法；当能够满足一个要求时，保证我们的资源尽可能早地被释放，以这种方式我们可以把留下来满足其他需求的时间最大化。
让我们把这个算法描述得更形式化一点，我们将用R表示既没有接受也没有拒绝的需求的集合，用A表示呗接受的需求的集合。至于算法怎样运行的例子见图4.2。
图4.2 区间调度算法的运行例子
4.1.2 分析算法
虽然这个贪心法是相当自然的，但它能返回一个最优的区间集合却不是显而易见的，的确，保留关于它的最优性的论断仅仅是一种感觉；导致前面那些并非最有贪心法的想法出事看来也能保证最优。
作为开始，我们可以立刻声明由算法返回的集合A中的区间是相容的。
命题4.1 A是一个相容的需求集。
我们需要证明的是这个解是最优的，因此，为便于比较，令O是一个最优的区间集合，理想的是可能要证明A=O，但这个要求是太过分了：可能存在许多最优解释，A至多与其中一个相等，因此我们不能这样作，儿童诗简单证明|A|=|O|，即A和O包含同样的区间个数，因此也是一个最优解释。
正如我们开始提出的，这个证明的主要思想是要找出这样一种认识，我们的贪心算法“领先”于这个解O，我们将把贪心算法构造部分解与解O初始的一段进行比较，并且证明贪心算法以一部介意不的方式做得更好。
为有助于证明我们引入某些符号，设,hellip;是A中的需求，并按照其加入到A的次序排列，注意|A|-k，类似地，设O中的需求表示为hellip;,，我们的目标是证明k=m，假设在O中的需求也按照对应区间的自然的左到右的次序排列，即开始与结束点的次序排列，注意O中的需求是相容的，这就推出这些开始点与结束点有着同样的次序。
我们关于贪心哒的直觉来自下述想法：当满足第一个需求以后，想要我们的资源尽可能早地被释放。的确，我们的贪心规则保证,这就是想要证明我们的贪心规则“领先”的认识-------它的每个区间至少在集合O中对应的区间结束的一样早，于是，我们现在证明对每个，这个算法的调度接受的第r个需求结束不迟于最优调度的第r个需求。
命题4.2 对所有的指标rle;k，我们有f()le;f()
证:我们将用归纳法证明这个论断，对于r=1，论断显然为真：算法由选择具有最小截止时间的需求i1开始。
现在令rgt;1，根据归纳假设，假定这个论断对r-1为真，我们将试图证明它对r也为真，正如图4.3所示，由归纳假设我们有,为了使算法的第r个区间不更早的结束，它必须“落后”，正如该图所示，有一个简单的理由使得它不可能发生。不选择一个结束迟的区间，贪心算法（最坏情况下）总可以选择jr，于是完成了归纳步骤。
我们可以更精确地如下表达这个论述，我们知道(因为O由相容的区间组成)，把他们与归纳假设组合，我们得到，于是当贪心算法选择时，此刻区间，是在有效区间的集合R中，贪心算法选择具有最小结束时间的有效区间；因为是这些有效区间中的一个，我们有，这就完成了归纳步骤。
图4.3 有关贪心算法领先的证明中的归纳步骤
于是我们已经把贪心算法保持领先于O的认识形式化了；对每个r，它选择的第r个区间至少在O中的第r个区间结束得一样早，我们现在看看为什么这就推出贪心算法的集合A是最优的。
定理4.3 贪心算法返回一个最优的集合A
证 我们现在再用反证法证明这个论断，恩uguoA不是最优的，那么一个最优几个O一定有更多的需求，即我们有mgt;k，对r=k应用命题4.2，我们得到。因为mgt;k，在O中存在一个需求,这个需求在结束之后开始，因此也在结束之后开始。所以在删除了所有需求,,hellip;,不相容的需求之后，可能的需求集合R仍旧包含，但是贪心算法停止在，而假设它仅当R为空时停止，产生矛盾。
实现与运行时间 如下所述，我们可以使算法以O（nlogn）时间运行。开始按结束时间对n个需求排序并且把它们标记成这个次序；即对我们将假设当ilt;j时,这用O（nlogn）时间，再用O（n）时间构造一个具有下述性质的数组S[1,2,hellip;.,n]:S[i]包含s(i)的值。
现在我们通过按f(i)增加的次序处理这些区间来选择需求，我们总是选择第一个区间；然后按次序迭带通过区间直到满足的第一个区间j，然后我们选择这个区间，更一般地说，如果我们当前刚选的区间在时刻f结束，我们继续迭代通过后来的区间直到第一个满足的j。以这种方式，我们对这些区间一次通过就实现了上面分析的贪心算法，二每个区间用常熟时间，于是，这部分算法用O（n）时间。
4.1.3 推广
我们这里考虑的区间调度问题是相当简单的调度问题。在实际背景中可能产生许多更加复杂的问题，在面指出一些问题，在本书的后面它们将以不同的形式展现在我们面前。
在这个问题的定义中，我们假定当调度算法选择相容于子集时它已经知道了所有的需求。当然可能自然想到这个问题的另一个版本中。其中调度员需要在获悉全部需求集合之前作出接受或者拒绝某个需求的决定，如果调度员为收集所有其他需求的信息而等得太久，那么顾客（需求者）可能会失去耐心，他们可能放弃并且离开，一个活跃的研究领域涉及到这种在线算法，它必须在不知道进一步输入的情况下随时间不断出决定。
4.1.4 一个有关的问题 ：调度所有的区间
问题：在区间调度问题中，存在一种单一的资源和以时间区间形式表示的许多需求，因此我们必须选择哪些需求被接收且哪些需求被拒绝，如果我们有许多相同的资源可用，而且我们想使用尽可能少的资源安排所有的需求，那么就产生一个相关的问题，由于这里的目标是把所有的区间划分到多个资源，我们将把它看做一个区间划分问题。
例如：假设每个需求与一个在特定时间区间教室里需要安排的课对应，我们想使用尽可能少的教室满足所有这些需求，因而在我们的安排下教室是多个资源，并且基本的约束是两个在时间上重叠的课必须被安排在不同的教室。采用等价的说法，区间需求也可以是需要在特定时间区间被处理的工作，而资源可能是能够处理这些工作的机器，在本书后面第十章，我们将看到这个问题的不同应用，其中区间是需要在一条光缆上被分配带宽的路由需求。
作为这个问题的说明，考虑在图4.4a中的例子，在这个例子中的需求用三个资源就可以全部被安排，这在图4.4b中给以说明，其中需求被重新排成三行，每行包含一组不重叠的区间。一般地，人们可以把使用k个资源的一个解想象成把这些需求按照k行不重叠的区间进行重新排列，第一行包含所有分配到第一个资源的区间，第二行包含所有分配到第二个资源的区间，等等
图4.4 （a）区间划分问题的一个实例，其中具有十个区间.（b）试用三个资源
安排所有区间一个解；每行代表一组可以全部安排到一个资源上的区间
现在，在这个范例中有任何希望仅使用两个资源吗？显然答案是没有，我们至少需要三个资源，例如，由于资源abc全都通过这个时间线上的一个公共点，因此他们都需要安排在不同的资源上，事实上，人们对区间划分的任何实例，一般地做出这个最后的论断，假设我们定义一个区间集合的深度是通过时间线上任何一点的最大区间数，那么我们说，命题4,4 在任何区间划分的实例中，资源数必须至少是区间集合的深度
证 假设区间集合的深度为d，且，，......全都通过时间线上的一个公共点，那么这些区间的每一个必须被安排到不同的资源上，因此整个实例至少需要d个资源。
我们现在考虑两个问题，他们原来是紧密相关的，第一，我们能设计一个有效算法用最少的资源来安排所有的区间吗？第二，是否总存在一个使用与深度等量资源的调度？实质上，对第二个问题的一个肯定回答意味着对区间划分的唯一障碍完全是局部问题 一组区间全堆在同一个点，是否不可能存在其他长范围的障碍把所需资源数堆得更高，对此不是立刻就能弄清楚的。
我们现在设计一个简单的贪心算法，使用与深度等量的资源安排到所有的区间，这立刻就可以推出这个算法的最优性，根据命题4,4 ，没有解能使用比深度还少的资源数量，因此，我们的算法分析将说明另一种证明最优性的一般方法：找到一个简
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[484295]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
