贪心算法是一类算法,它反复按照指定规则作出看起来最好的选择,逐步构造解,而不系统地重新考虑先前的选择。它广泛应用于数学优化,即在约束条件下使目标最大化或最小化。对于某些问题,贪心法能够得到最优解;对于另一些问题,它能够得到具有可证明保证的近似解;而在没有已知保证时,它可能只能得到看似合理的解。贪心法是否有效,取决于局部选择规则与问题整体结构之间的关系。
基本原理
贪心法通常维护一个部分解,并反复执行以下三项操作:
- 确定当前可用的选择。
- 按照局部准则选出最优的选择。
- 如果该选择满足相关约束,就将其确定下来。
对于从有限集合中选取元素的问题,一种常见的框架是:
解 ← 空集
按照贪心准则排列候选项
依次遍历排序后的每个候选项:
如果加入该候选项后仍满足可行性要求:
将该候选项加入解
返回解
这一框架并非适用于所有情况。有些算法会反复合并对象、更新优先级,或将暂定值确定为最终值,而不只是向集合中添加元素。其本质特征是直接采纳局部最优的决策,而不是系统地探索其他可能的决策序列。
“最优”由算法定义,并不存在通用的衡量标准。贪心规则可能优先选择最早结束的任务、费用最低的合格边、单位重量价值最高的物品,或者当前已知距离最小的顶点。对于同一个问题,不同规则可能产生截然不同的结果。
可行解不一定是最优解。极大解也不一定是最大解:极大集合是指在保持可行性的前提下,无法再向其中添加元素的集合;最大集合则是指元素个数达到可能的最大值的集合。
最优性条件
在解释能够求得精确最优解的贪心算法时,通常会涉及两种性质。
贪心选择性质
对于某个指定规则,如果存在一个最优解与该规则作出的选择相容,就称问题具有相对于该规则的贪心选择性质。作出选择后,算法留下的剩余问题还必须能够继续适用同样的推理。
这是一个需要严格论证的数学命题。某个选择看起来很有吸引力,或者在一些示例上效果良好,并不能证明该性质成立。
最优子结构
如果一个问题的最优解能够由恰当定义的子问题的最优解组合而成,就称该问题具有最优子结构。
仅有最优子结构并不足以证明贪心算法正确。许多问题虽然具有这一性质,却需要使用动态规划,对多个备选方案进行比较,而不是立即确定其中一个。还需要回答的问题是:贪心选择能否安全地排除其他备选方案。
证明方法
证明贪心规则安全时,常用的论证方式有:
- **交换论证:**从一个最优解出发,将其中的一项决策替换为贪心决策,并证明可行性不受影响,目标值也不会变差。然后对剩余问题重复这一论证。
- **领先性论证:**逐步比较贪心算法与另一个解所作出的选择,并证明按照某种恰当的衡量标准,贪心构造的结果始终不会落后。
- **结构性安全性质:**建立定理,指出哪些选择总能属于某个最优解,例如图中跨越某个适当割的最小权重边。
这些论证往往可以写成归纳证明。在程序验证中,相应的安全性命题可以表述为循环不变量,例如“已选边能够扩展为一棵最小生成树”。
典型示例
区间调度
在无权的区间调度问题中,每项任务占用一个时间区间,目标是在同一个资源上选出尽可能多的、彼此不重叠的任务。
一种能够得到最优解的贪心规则是:反复选择与已选任务兼容且结束时间最早的任务。如果任务占用半开区间 ,那么只要一项任务的开始时间不早于前一项任务的结束时间,它就可以接在前一项任务之后。
交换论证从某个最优调度方案中的第一项任务入手。将其替换为最早结束的任务,不会减少留给后续任务的可用时间。剩余的选择问题仍具有相同形式。
按结束时间对任务排序需要 时间,随后进行一次线性扫描。如果任务已经排好序,扫描只需 时间。
其他看似合理的规则一般并不成立。选择持续时间最短的任务,或开始时间最早的任务,都不一定能使选出的任务数最多。在各任务收益不同的加权版本中,同样的规则通常也不适用;这类问题一般使用动态规划求解。
最小生成树
连通无向加权图的最小生成树连接所有顶点,不包含环,并且边的总权重最小。
两种经典的贪心方法是:
- **克鲁斯卡尔算法:**按照权重非递减的顺序处理各条边;如果一条边连接两个此前互不连通的连通分量,就将其加入。
- **普里姆算法:**从一棵树开始,反复加入连接树内顶点与树外顶点的最小权重边,使树逐步扩展。
这两种算法的正确性来自生成树的结构性质。具体而言,跨越某个恰当选取的割的最小权重边可以安全地加入。相同的边权可能使最优树不唯一,但不会使这些方法失效。
迪ijkstra算法
迪ijkstra算法用于求解边权非负的图中的单源最短路径问题。它反复从尚未处理的顶点中选出暂定距离最小的顶点,并确定其最终距离。
边权非负使这一步骤具有安全性:之后经过距离更远的未处理顶点的路径,不可能缩短刚刚确定最终距离的顶点的距离。如果存在负权边,这一保证便不再成立。贝尔曼–福特算法等算法能够在不同的适用条件下处理负权边。
借助适当的优先队列,迪ijkstra算法能够在距离估计值不断变化时,高效地选出下一个顶点。
霍夫曼编码
霍夫曼编码为频率已知的符号构造最优二进制前缀码,其标准目标是使加权码字长度最小。它反复将权重最小的两个对象合并为一个新对象,新对象的权重为两者之和。
这一局部步骤之所以成立,是因为总存在一棵最优编码树,使两个权重最小的符号位于最大深度处的一对兄弟叶节点上。将它们合并,就能把问题归约为规模更小的实例。
这个例子表明,贪心法的候选集合可以在构造过程中不断变化,而不必始终按某个固定顺序处理。
分数背包
在分数背包问题中,物品 的价值为 ,重量为正数 ,可选取的比例为 。目标为
约束条件为
当价值非负时,按照价值密度 非递增的顺序选择物品,并对每件物品尽可能多取,即可得到最优解。
对应的 0–1 背包问题要求 ,即物品不可分割。此时,同样的规则可能失效。例如,容量为 ,三件物品的重量与价值分别为 、 和 。按价值密度排序会选取前两件,总价值为 ;而选取后两件的总价值为 。
结构理论:拟阵
拟阵提供了一种严格的数学框架,在这一框架下,一大类贪心选择方法都能保证正确。
有限拟阵由一个底集 和一个独立子集族 构成,并满足:
- 空集属于 。
- 独立集的每个子集都是独立集。
- 如果 且 ,那么可以将 中的某个元素加入 ,同时保持独立性。
第三个条件是一种交换性质。当元素权重非负时,按照权重非递增的顺序处理元素,并在保持独立性的前提下接纳每个元素,就能得到最大权重独立集。
反过来,在有限遗传集系统中,如果这一算法对任意非负权重赋值都正确,那么该系统就是拟阵。这解释了为什么一些表面上相似的选择问题,在是否适合使用贪心法方面可能有显著差别。
无向图中的森林构成图拟阵的独立集,这将该理论与生成树算法联系起来。拟阵并不能涵盖所有成功的贪心算法;例如,区间调度的正确性依赖于另一种交换结构。
近似算法与启发式应用
无法得到精确最优解,并不意味着贪心法毫无用处。近似算法能够对结果偏离最优解的程度给出可证明的界。启发式方法即使没有这样的界,也可能具有实际用途。
对于无权的集合覆盖问题,一种标准的贪心算法会反复选择能够覆盖最多尚未被覆盖元素的集合。对于包含 个元素且能够被覆盖的全集,该算法所得解使用的集合数不超过最优解的 倍,其中
贪心启发式方法也用于调度、路径规划、特征选择和搜索等领域。例如,用于旅行商问题的最近邻规则能够快速构造一条路线,但不一定能得到最短巡回路线。
近似保证只适用于满足特定假设的特定算法,不能仅凭“贪心”这一标签推断出来。
效率与实现
贪心算法通常效率较高,因为它们避免了枚举完整解,但采用贪心设计并不意味着算法必然具有某种特定的时间复杂度。
常见的开销包括:
- 对候选项排序,通常需要 时间。
- 维护堆或其他优先队列。
- 检验某个拟议选择是否保持可行性。
- 每次选择后更新候选项的评分。
因此,数据结构的选择可能成为决定性能的主要因素。例如,克鲁斯卡尔算法需要高效地跟踪连通分量,而霍夫曼编码则需要反复提取权重最小的对象。
并列情况的处理方式可能影响最终返回哪个解。如果正确性证明允许任意处理并列情况,那么这些结果都仍然具有相应保证。对于未经证明的启发式方法,并列情况的处理方式可能显著影响解的质量。
与其他算法方法的关系
贪心算法与几种相关方法有所不同:
- 动态规划保留并比较多个子问题的解;贪心法则直接采纳局部选出的方案。
- **分治法**将问题拆分成若干子问题,再合并它们的解,但不一定使用贪心选择。
- **回溯法**在探索其他可能方案时会重新考虑先前的决策;基本的贪心构造则不会这样做。
- **局部搜索**通常从一个完整解出发,通过邻近修改加以改进;构造型贪心法则通常逐步建立一个解。
贪心选择也可以只是更大算法中的一个组成部分,与搜索、随机化或改进步骤结合使用。
历史发展
早在贪心思想被确立为一种统一的算法设计范式之前,人们就已经在使用这类推理。几个典型例子出现于二十世纪中期:霍夫曼编码发表于 1952 年,克鲁斯卡尔生成树算法发表于 1956 年,普里姆对其算法的阐述发表于 1957 年,迪ijkstra最短路径算法发表于 1959 年。一些生成树思想则有更早的源头。
此后,组合优化领域的研究,尤其是拟阵理论,阐明了反复作出局部选择在什么条件下必然能够得到全局最优解。区分“可证明安全的选择”与“直觉上有吸引力的选择”,至今仍是贪心算法分析的核心。