贪心算法的分类
S.A. Curtis
牛津布鲁克斯大学计算系，牛津OX33 1HX，英国
2003年4月22日收到; 收到修订后的2003年9月5日; 2003年9月22日接受
摘要
本文介绍了用于优化的贪婪算法的分类原则问题。这些原则通过它们在关系演算中的表达而变得精确，并且通过各种例子说明。 讨论将此工作与其他贪婪算法进行了比较。
c 2003 Elsevier B.V. All rights reserved.
MSC: 68R05
关键词：贪心算法
- 简介
是什么让算法变得贪婪？ 文献中的文献略有不同，但大多数情况都不同将贪婪算法描述为一个选择序列，每个选择都是在某种程度上当时最好的（贪婪一词指的是选择最好）。 在做出选择序列时，贪婪的算法永远不会重新开始早先的决定。
由于它们的简单性，贪婪算法通常很简单和高效。 它们也非常通用，可用于许多人的不同问题各种组合学领域及其他领域。 应用程序的一些示例包括数据压缩和DNA测序[16,23,25]，找到最低成本生成树加权无向图[24,30,34]，计算几何[17]和路由通过网络[20]，仅举几例。
有些问题不能完全解决，但可能有一个贪婪的算法可以用作启发式算法，接近最优的解决方案。 对于其他问题，贪心算法可能会产生精确的解决方案。 不幸的是，对于任何特定问题，不能保证存在贪婪算法来完全解决它。 因此，算法设计者认为合理的贪婪策略可以解决问题可能会使贪婪算法的理论变得有用：可以测试正确性条件，看看特定的贪婪算法是否提供了精确的解决方案。
现有的贪婪理论经常解决以下问题：
bull;表达贪婪算法。
bull;贪婪算法的正确性证明。
bull;贪婪数据结构的表征。
bull;合成贪婪算法。
bull;覆盖尽可能多的贪婪算法。
不同的贪婪理论集中在对上述问题的不同选择上。 拟阵理论[15,37]和后来的贪婪[27-29]，使用集合系统模拟贪心算法，主要集中于贪婪数据结构的特征（贪婪算法产生最优解的问题结构），但是 根本不考虑贪婪算法的综合。 一些理论，如Helman的k-ary支配关系[18]，以及他与Moret和Shapiro [19]的合作，试图通过推广所考虑的贪婪数据结构来涵盖更多贪心算法。其他理论集中在贪婪的表达 - 诸如Charlier [9]的工作，以及Bird and de Moor [2,3,4,6]的工作。 后者通过使用分类数据类型来表征贪婪结构，并侧重于在这些数据类型上使用catamorphisms和anorporphisms来表达和开发贪婪算法。
到目前为止，贪婪的理论在解决前四个方面取得了很大进展上述问题，但没有一个成功地融入所有贪婪算法。
本文的工作目标是（按顺序）：
（1）覆盖所有解决优化问题的贪婪算法。
（2）贪婪结构的表征。
（3）算法开发的正确性证明和设计灵感。
（4）简单表达贪心算法。
本文介绍了该工作的结果：一个用于优化问题求解的贪婪算法的综合理论，它提供了四个一般原则，即对贪婪算法进行分类并协助证明其正确性。 该理论不包括贪婪的启发式方法，也没有解决非优化问题的问题：它的范围是贪婪算法，为优化问题提供最佳解决方案。
这项工作的介绍分为三个部分。 在第2节中，非正式地介绍了四种贪婪原则，以便在抽象层面上提供可读的介绍。第3节在关系演算中正式表达了这些原理，并用贪婪算法的几个例子进行了说明。 最后，在第4节中，讨论了这项工作并评估。
- 非正式概述
在本节中，通过示例非正式地陈述了四个贪婪原则。 这个单独的概述强调，这些原则并不依赖于可能表达贪婪算法的恶意行为
2.1．贪婪算法的术语
优化问题通常由其潜在解决方案的描述以及用于判断哪个是最佳的标准来指定。 该标准将被称为全局最优性标准。如前所述，贪婪算法产生一系列选择，每个选择在某种程度上是当时最好的。 判断什么是贪婪选择最佳的标准将被称为局部最优性标准。随着贪婪算法的进展，每个选择都需要朝着构建问题的解决方案迈出一步。 这样的步骤将被称为构造步骤。 意图是构造步骤的作用（与贪婪算法中使用的方式无关）是能够生成所有可能的解决方案。优化问题，通过以所有可能的方式将构造步骤重复应用于输入。关于这种结构，术语“完成的解决方案”将用于表示完全完成的问题的潜在解决方案，可能是也可能不是关于全局最优性标准是最优的。 相比之下，术语“偏”解决方案将涉及部分构建的潜在解决方案（可能会也可能不会完全建造）。
以下是两个例子来说明：
Kruskal的算法（见[30]）是一个众所周知的贪婪算法具有边缘成本的无向（连通）图中的最小成本树。 它从一组空边开始，然后在每个阶段添加一条边该集合使得到目前为止收集的边缘之间没有创建循环。 边缘在每个步骤中选择的是最低成本之一。
对于该算法，非循环边集是局部解和边集形成图的生成树是完整的解决方案。 此外，
构造步骤：向边集添加非循环创建边。
局部最优性标准：选择的边缘应该是最低成本。
全局最优性标准：边缘集的成本之和应为尽可能小。
对于Kruskal的算法，局部最优性标准可以被重新描述与全局最优性标准相同。 这是因为选择添加时非循环创建边缘到集合，最小化边缘成本的总和是相同的目标是尽量减少边缘成本的增加。 虽然通常可以以与全局标准相同的方式重新定义本地标准，有时它不是。 以下示例演示了两个最优性标准可能非常不同：
硬币变化问题（见[7,8]）涉及选择尽可能少的硬币可以加起来给定的值。 对于某些货币（例如，与denom-{1; 2; 5}times;10 n; nisin;{0; 1; 2; 3; 4}），以下贪心算法有效：at每一步选择最大值的硬币，不超过剩余的金额。例如，为了弥补45c的值，硬币20c，20c，5c将是按此顺序选择。
对于该算法，不超过给定值的硬币收集是部分的解决方案和硬币收集总计恰好给定的值是完成的解决方案。 此外，
施工步骤：为目前为止选择的那些添加一枚硬币，使其值得选择的硬币不会使总数超过给定值。
局部最优性标准：所选择的硬币应具有最大值。
全局最优性标准：所选硬币的总数应该尽可能小尽可能。
在贪婪的硬币改变算法中，全局最优性标准是非常不同的从局部最优性标准，并说明一个共同的主题：一个最佳的解决方案需要尽可能少的构造步骤，相反，贪婪的选择尝试尽可能多地取得进展。
贪婪算法可以解决许多问题，包括different global和当地标准。 例如，以下问题也使用全局最优性标准最小化施工步骤的数量：最小的升级[1]，字典编码[5,36]，迈达斯教授[10]（后面也会看到）和拉力赛车手[11,14]。 在相比之下，一些问题使用全局最优性标准最大化con数量施工步骤，例如活动选择[10]和Marble Mingling [11-13]问题。 如果全局标准要么最小化或最大化con的数量施工步骤，那么地方标准必须与全球标准不同标准。 此外，一些贪婪算法具有不同的全局和局部最优 - 全球标准与建设步骤无关的标准例如Amoeba Fight Show问题[32]。
事实上，局部最优性标准通常不同于全局最优性标准很重要：几种理论不包括这种可能性，因此排除在外许多贪婪的算法。
2.2．四个贪婪的原则
下图说明并描述了四种贪婪原则（箭头是影响）：
这些原则描述了最优性标准与最优标准之间的可能关系施工步骤。 每个贪婪算法都能产生最佳解决方案优化问题将满足最佳全球原则，但可能会或可能不会 - 任何其他人都是如此。 现在，这些原则是非正式地单独简单描述的讨论了。
2.2.1．Best-Global
Best-Global原则实际上是说贪婪算法的条件在第一个地方工作。 也就是说，每个贪心算法都能找到最优解优化问题符合这一原则。 它可以用文字描述如下：
Best-Global：考虑一个部分解决方案，这是贪婪的直接结果选择（即，关于局部最优性的最佳部分解决方案标准，执行建设步骤的替代方式）。 相比完成任何其他替代方案，完成这个最好的部分解决方案至少与全局最优性标准一样好。
这种情况经常被用作个人贪婪算法的证明方法 ：通常将完整的解决方案转换为第二个完整的解决方案，第二个解决方案是从一个贪婪的选择开始构建的。 就是这样表明，就全局最优性而言，第二个并不比第一个差通过这种方式，可以证明贪婪选择的部分解可以完成至少与其他已完成的解决方案一样好。
关于这种全球状况的一个重要特征是最优性只是保证 - 为完成的解决方案做准备：它可能是一个部分解决方案贪婪算法的中间阶段不是最优的。
每个贪婪算法都能为优化问题提供最佳解决方案，满足这个Best-Global原则，并且有许多正确的例子 - 在整个文献中遵循这种模式的证明。 例如，在霍洛维茨等人的书[22]，上述原则的具体实例是作为一种方式给出的证明贪心算法是正确的，这用于表示Kruskal的正确性算法。
2.2.2Better-Global
Better-Global原则类似于Best-Global，但更强：
Better-Global：考虑两个部分解决方案（制定可能的替代方案）贪婪的选择），第一个优于第二个优于当地的选择恶意标准。 鉴于第二种选择的任何完成，都有一个完成第一个替代品，至少与全球最优性一样好标准。
Better-Global条件，如Best-Global条件，考虑如何部分解决方案的优点a：完成它们的完成。 但是，最好的全球会议解决了最好的替代方案，而Better-Global条件解决了这个问题两种替代方案，一种比另一种更好。 因此，Better-Global原则是很少用于正确性证明，因为它是一个更强的条件（两个部分解决方案中更好的也不能被认为是最好的）因此证明并不容易。
需要注意的一点是，“更好”是以非严格的方式使用：描述“至少和”一样好“会更贴切，但不那么简洁。
满足Better-Global条件的贪婪算法的一个例子如下：
迈达斯教授的驾驶问题（来自[10]）涉及汽车之旅的计划沿着特定路线。 特别是，教授希望选择哪些加油站沿着这条路停下来，为了用汽油把汽车的油箱拿起来。 汽车坦克可以容纳足够的汽油，以达到一些修正的距离，整体教授迈达斯想尽可能少停下来。
如果通过决定停止哪些服务站来构建旅程计划，从起点开始按顺序做出决定，然后是贪心算法“在停止汽油之前总是尽可能地去”工作。
这满足了Better-Global的条件：当教授在服务站时考虑到下一站，选择更远的车站，与a相比更接近一个，o：有一个较少（或相等）停靠次数的旅程的可能性。（见证明。）
满足Better-Global条件的贪婪算法的另一个例子是一个解决最大延迟问题（参见[21,31]），这将在后面给出定理2（更好全球化）的插图。
2.2.3. Best-Local
其余两个原则更关注局部最优性标准，以及如何作为贪婪算法保持关于该标准的最优性进展。
Best-Local：在贪婪算法运行期间，部分解决方案就是到目前为止，就局部最优性标准而言，迄今为止仍然是最好的应用贪婪的步骤。 另外，关于局部最优性的最优性标准必须意味着也实现了全局最优性。
需要注意的一点是，并非所有贪心算法都可以考虑遵守最佳本地原则。 贪婪的步骤只考虑立即单个部分解决方案的可能选择，因此局部最优性标准是只需要能够比较这些选择; 但是上述原则要求局部最优性标准，可以更一般的方式比较部分解。最好通过示例说明。 首先，以局部最优性为例标准可以推广，最佳本地原则确实适用：
Kruskal的算法（如前面2.1节所述）发现最低成本通过重复选择最小的非循环创建边来生成图的树成本，添加到目前为止选择的那些。 这里是局部（和全局）最优性标准是最小化边缘成本的总和。 Kruskal的算法满足最佳 - 局部原理，因为经过n步的算法，形成了非循环子图是一种成本最低的，在选择n边形成的所有可能方式中非循环子图。 因此，这导致整体的最小成本生成树（连接）图。
其次，这里是一个可以推广局部最优性标准的例子，但最佳本地原则并不成立：
Prim的算法（参见[24,34]）是另一个众所周知的贪婪算法具有边缘成本的无向连通图中的最小成本生成树。 它也可以从一组空边开始，在每个阶段添加一个最小值到目前为止收集的成本优势。 然而，与Kruskal的算法不同，它选择了它非周期创建边缘仅来自与目前为止收集的边缘相邻的边缘。
局部和全局最优性标准与Kruskal算法的标准相同，即最小化到目前为止收集的边缘的成本之和。 它是通过边缘选择的限制来构建步骤。
Prim的算法不满足Best-Local原则，就像之后创建的树一样n个步骤不一定是所有n个边缘的最低成本树。 对于例如，请考虑以下图表，并将起始节点指定为v 6
在Prim算法的三个步骤之后，将形成树{（v 6; v 7）;（v 5; v 6）;（v 1; v 5）}。然而
英语原文共 33 页，支付完成后下载完整资料
资料编号：[3225]
