1 基本概念
1.1 定义与核心思想
贪婪算法是一类在求解过程中，每一步都选择当前看来最优的方案的算法思想。这里的“最优”通常是相对于当前状态而言的局部最优，而不是对整个问题空间进行全面搜索后的全局最优。
这类方法的核心在于：一旦做出选择，通常不再回头修改。算法通过连续累积多个局部决策，逐步逼近问题的可行解，有时还能直接得到最优解。由于决策过程往往较为直接，贪婪算法常具有实现简单、运行效率高的特点。
不过，贪婪策略并不天然适用于所有问题。只有当问题结构满足特定条件时，局部最优选择才可能推导出整体最优结果。
1.2 贪婪选择性质
贪婪选择性质指的是：在问题的最优解中，某个局部最优选择总能被证明属于某个全局最优解的一部分。换言之，先选当前最优的那一步，不会破坏最终得到最优解的可能性。
这是贪婪算法成立的关键前提之一。若一个问题具备这一性质，就可以在每一步安心做出当前最佳选择，而无需担心“早选错一步导致后面无解”。
证明贪婪选择性质通常需要结合问题本身的结构进行分析，常见方法包括交换论证、归纳和反证等。
1.3 最优子结构
最优子结构是指：一个问题的最优解包含其子问题的最优解。也就是说，把原问题拆分为若干子问题后，只要整体最优，就要求各个子部分也分别达到最优。
这一性质不仅是贪婪算法的重要基础，也广泛出现在动态规划中。不同之处在于，贪婪算法强调“当前一步怎么选”，而动态规划更重视“子问题如何组合”。
如果一个问题只有最优子结构而没有贪婪选择性质，那么单靠贪婪策略通常不够，需要借助更全面的搜索或状态转移方法。
1.4 局部最优与全局最优
局部最优是指在当前阶段、当前约束下最有利的选择；全局最优则是对整个问题而言最优的结果。两者并不总是一致。
贪婪算法的挑战，就在于判断“眼前最好的选择”是否真的会导向整体最优。有些问题里，局部最优会不断累积成全局最优；另一些问题里，局部看起来很划算的决策，最终却可能使整体结果变差。
因此，贪婪思想并不是“总选最好的就行”，而是“在能保证正确性的前提下，优先选当前最优”。这也是贪婪算法与简单经验法则的重要区别。
2 算法设计方法
2.1 选择标准的建立
设计贪婪算法时，首先要明确每一步依据什么标准做选择。这个标准通常来自问题的目标函数，例如最小化代价、最大化收益、尽快完成任务等。
选择标准的建立往往决定算法能否成功。一个好的标准应当与问题的最优结构紧密对应，并且能够在每一步迅速比较候选项的优劣。
2.2 候选解的排序策略
很多贪婪算法会先对候选元素进行排序，再按某种顺序逐个处理。排序的作用，是把潜在的优先级显式化，从而让后续选择更直接。
常见排序依据包括结束时间、权重、收益比、距离、边的代价等。排序并不一定是算法本身的目标，但常常是为了简化贪婪判断，让“当前最优”变得容易识别。
2.3 可行性判断
贪婪算法不仅要选“看起来最好”的对象，还要确保该选择不会破坏约束条件。可行性判断就是用来确认当前候选是否还能保持解的合法性。
例如，在区间调度中，选择一个新任务前要检查它是否与已选任务冲突；在最小生成树构造中，要判断新边是否会形成环。若只顾局部收益而忽视可行性，就可能得到非法解。
2.4 终止条件设计
贪婪算法通常在满足某个终止条件时停止，例如已选元素数量达到要求、所有候选项都已处理完毕，或再无可行候选可选。
合理的终止条件能避免算法过早结束或无限循环。它通常与问题目标直接对应，既要保证解的完整性，也要避免多余操作。
3 正确性证明
3.1 交换论证
交换论证是证明贪婪算法正确性最常见的方法之一。其基本思路是：假设存在一个最优解不是按贪婪策略构造的，然后证明可以把其中某个非贪婪选择替换成贪婪选择，而不降低解的质量。
如果这种交换总能成立，就说明贪婪选择不会比最优解更差，从而可逐步把任意最优解转化为包含贪婪步骤的形式。最终可证明贪婪算法确实能得到最优解。
3.2 归纳证明
归纳证明常用于那些可以按规模递推的问题。证明时先验证最小规模情形成立，再假设规模较小的子问题已经正确，进而推出更大规模问题也成立。
对于贪婪算法，归纳法通常用于说明：当第一步贪婪选择正确时，剩余部分仍是同类问题，于是可重复应用同样的策略。这种结构在区间调度、哈夫曼编码等问题中较为常见。
3.3 反证法
反证法的思路是：先假设贪婪策略不是最优的，然后推导出矛盾。矛盾可能来自问题约束、目标值比较，或与已知最优结构冲突。
这种方法适合在贪婪选择性质比较明显时使用。它不一定直接构造替换过程，但能从逻辑上说明“若不按贪婪方式做，就会比某个可行方案更差”，从而支持正确性结论。
3.4 证明中常见陷阱
贪婪算法的证明中，常见错误包括把“看起来合理”误当成“已经证明”、忽略约束变化、以及把局部最优与全局最优直接等同。
另一个常见问题是，只证明了某一步选择合理，却没有说明这种选择之后剩余问题的结构不变。若缺少这一步，就无法保证算法可以持续应用同一策略。
4 经典应用
4.1 区间调度问题
区间调度问题通常要求从一组时间区间中选择尽可能多的互不重叠区间，或在带权版本中优化某种总收益。它是贪婪算法的经典例子之一。
这类问题的关键在于：如何在多个看似可行的任务中，选出最不妨碍后续安排的一个，从而保留更多后续空间。
4.1.1 按结束时间最早选择
对无权区间调度而言，常用策略是优先选择结束时间最早的区间。这样做的直觉是：越早结束，越能给后续区间留下安排余地。
该策略之所以有效，是因为它尽量减少对时间轴后续部分的占用，从而提高可容纳区间的总数。它也是贪婪选择性质在调度问题中的典型体现。
4.1.2 按开始时间或长度排序的对比
按开始时间最早排序看似自然，但往往不是最优策略。因为一个很早开始、持续很长的区间，可能会占据大量资源，反而减少总选择数。
按长度最短排序也不一定正确。短区间不代表更有利，关键仍在于它对整体可安排空间的影响。与结束时间策略相比，这两种排序缺少对“后续可扩展性”的直接保证。
4.2 哈夫曼编码
哈夫曼编码是一种构造最优前缀码的方法，常用于数据压缩。它的目标是在符号出现频率已知的情况下，尽量减少平均编码长度。
这一问题的核心思想是：频率高的字符用较短编码，频率低的字符用较长编码，从而在整体上降低总成本。
4.2.1 最优前缀码构造
哈夫曼编码通过反复合并频率最小的两个节点，逐步建立一棵二叉树。每次合并都把两个最不常用的符号或子树组合起来，使其共同承担更深的层次。
这种构造之所以有效，是因为最小频率元素放在较深位置对总成本影响最小。最终得到的树对应一组前缀码，且在所有前缀码中具有最优平均长度。
4.2.2 优先队列的使用
哈夫曼算法通常借助优先队列维护当前最小频率的节点。这样，每次都能快速取出频率最小的两个元素，完成合并后再插回结构中。
优先队列的引入使算法从“每轮扫描找最小值”的低效做法，变成更适合大规模输入的高效流程，是工程实现中非常关键的数据结构。
4.3 最小生成树
最小生成树问题要求在连通加权图中选出一组边，使所有顶点连通且总权值最小。它是图论中贪婪思想的重要应用。
这类问题体现了“每次选代价最小且不破坏整体结构”的原则。只要选择的边不形成环并保持可扩展性，就可能逐步构造出最优树。
4.3.1 Prim算法
Prim算法从一个起点开始，不断选择连接当前树与外部顶点的最小权边。它的思路是从局部扩展到整体，像“长树”一样逐步覆盖所有顶点。
该算法适合稠密图或能高效维护边权最小值的场景。每一步都保持已选边构成一棵树，因此天然满足可行性要求。
4.3.2 Kruskal算法
Kruskal算法则先将所有边按权重从小到大排序，再依次考虑是否加入生成树。若一条边不会形成环，就将其加入；否则跳过。
这种方法更像“全局挑边”，重点在于优先使用代价最低的边，同时通过并查集等结构避免出现环。它与Prim算法的选择方式不同，但目标一致。
4.4 单源最短路径的特殊情形
在某些特殊条件下，最短路径问题也可以使用贪婪思想求解。典型场景是边权非负时，通过不断确定当前距离最小的未访问顶点来扩展结果。
这类方法并不是对所有最短路问题都成立，但在满足条件时能以较高效率获得正确解。
4.4.1 权值非负条件下的贪婪策略
当图中边权非负时，一旦某个顶点的当前最短距离被确定，就不需要再回头修改。因为之后通过其他路径绕回来的代价只会更大或相等。
这一性质使得贪婪式推进成为可能。每次选取距离源点最近的未确定顶点，然后松弛其邻边，最终可得到从源点到各点的最短距离。
5 与其他算法思想的关系
5.1 与动态规划的区别
动态规划通常保存子问题结果，并通过状态转移寻找全局最优；贪婪算法则在每一步直接做局部最优选择，不保存大量中间状态。
两者都可能利用最优子结构，但动态规划更全面，适用范围也更广。代价是实现与计算通常更复杂。贪婪算法则更简洁，但正确性依赖条件更强。
5.2 与分治法的区别
分治法强调把原问题拆成彼此相对独立的子问题，再递归求解并合并结果。贪婪算法则更关注逐步决策，通常不需要复杂的合并过程。
如果说分治重在“拆开处理”，那么贪婪更像“边看边选”。它不追求把问题完全分解，而是利用问题结构直接前进。
5.3 与回溯法的区别
回溯法会尝试多种可能，并在发现错误或不可行时退回上一步；贪婪算法一般不回头，做出选择后立即继续。
因此，回溯更接近搜索，适合解空间较大但需要完整探索的问题；贪婪则偏向快速求解，牺牲了部分全面性，以换取速度与简洁性。
5.4 与启发式算法的联系
贪婪算法与启发式算法在表面上很接近，都可能依赖经验性的选择规则。不同的是，贪婪算法通常带有明确的正确性证明目标，而启发式方法更多追求“效果好”，不一定保证最优。
也可以说，贪婪策略常是启发式的一种严格形式。当贪婪选择能被证明正确时，它不再只是经验规则，而成为正式算法设计的一部分。
6 常见贪婪策略类型
6.1 先排序后选择
这是最常见的贪婪模式之一。先按某个关键指标对候选对象排序，再按顺序逐个检查并决定是否选择。
这种方式的优点是实现清晰、可验证性强，适合那些“优先级明确”的问题。例如按结束时间、权重或代价排序后处理，往往能简化决策流程。
6.2 按收益比或权重比选择
在某些优化问题中，单看收益或单看代价都不够，需要考虑单位成本带来的收益。收益比或权重比就是常见的比较标准。
这类策略常用于资源受限的情形，例如在有限容量内尽量获得更高回报。需要注意的是，比例型贪婪并不总是严格正确，必须结合问题结构判断。
6.3 按时间、距离、代价选择
许多调度和路径问题都可以用时间、距离、代价作为贪婪指标。选择更早完成、更近的目标或更低成本的边，往往能减少后续负担。
这种策略的直觉很强，容易理解，也便于实现。但“最小时间”或“最短距离”是否真是正确标准，仍要看问题本身是否支持这种局部选择。
6.4 按边或节点扩展选择
图问题中常见的贪婪方式，是按边或节点逐步扩展。例如从已有结构向外选取最合适的边，或从当前最有希望的节点继续推进。
这类方法强调“边扩展边维护可行结构”，因此常与堆、并查集等数据结构配合使用，形成高效实现。
7 适用条件与局限性
7.1 适用问题的特征
适合贪婪算法的问题通常具有明确的局部优先级，并且局部选择不会破坏整体最优结构。换言之，问题的正确解往往能够由一系列不冲突的最优局部决策组成。
如果问题还具有较强的单调性、可交换性或前缀可扩展性，贪婪策略就更容易成立。
7.2 不适用问题的典型表现
若一个问题中，当前看似最优的选择可能严重限制后续空间，贪婪算法往往失败。尤其当后续决策会反过来影响前面选择的价值时，单步局部判断就不够了。
这类问题常需要更完整的状态记录，或者需要搜索多种方案后再比较，而不是直接锁定一个局部最优。
7.3 近似解与次优解
在一些复杂问题中，贪婪算法虽然不能保证最优，但仍然可以作为高质量近似方法。它们通常能在较短时间内给出可接受的结果，尤其适合大规模数据场景。
因此，贪婪法不仅是“求精确最优”的工具，也常是“快速获得较好答案”的实用方案。
7.4 失败案例分析
贪婪失败的典型原因，是局部选择标准与全局目标不一致。例如某个选项当前收益最高，但它占用了关键资源，导致后面更有价值的组合无法实现。
这类失败说明：贪婪策略的直觉并不能替代证明。一个算法是否正确，最终要看它与问题结构是否真正匹配。
8 复杂度分析
8.1 时间复杂度
贪婪算法的时间复杂度通常较低，常见瓶颈来自排序、堆操作或可行性检查。若每一步都能在常数或对数时间内完成，整体效率往往较好。
与需要大量状态枚举的算法相比，贪婪法常显得更轻量。它的优势之一，就是把复杂搜索压缩成连续的局部决策。
8.2 空间复杂度
贪婪算法通常只需维护当前状态和少量辅助结构，因此空间开销不一定很大。若使用优先队列、并查集或若干标记数组，空间复杂度也多为线性或接近线性。
不过，具体空间大小仍取决于问题规模和实现方式。若输入本身需要排序或缓存，额外空间也会相应增加。
8.3 排序对复杂度的影响
排序常常是贪婪算法中最主要的预处理步骤。很多算法的总复杂度实际上由排序主导，例如从线性选择提升到整体的对数线性级别。
如果候选集合很大，排序成本就会明显影响效率。因此，设计时需要判断排序是否必需，是否能用更适合的结构替代。
8.4 数据结构对复杂度的影响
数据结构的选择会显著影响贪婪算法的性能。优先队列适合维护动态最值，堆能高效支持插入与删除最小元素，并查集则适合处理连通性判断。
合适的数据结构往往能把原本较慢的选择过程压缩到更高效的时间范围内，是贪婪算法工程实现中的重要组成部分。
9 实现与工程实践
9.1 伪代码写法
贪婪算法的伪代码通常结构清晰：初始化候选集，按规则排序或建立优先结构，循环选择当前最优项，检查可行性并更新状态，直到达到终止条件。
这种写法适合表达“选择—判断—更新”的流程，也方便验证每一步是否符合预期。
9.2 优先队列与堆结构
优先队列是实现贪婪算法的常用工具，尤其适合需要频繁取出当前最小或最大元素的场景。堆结构通常可在对数时间内完成插入和删除操作。
在哈夫曼编码、最短路和某些调度问题中，堆结构能大幅提高效率，使“每步找最优”不再成为性能瓶颈。
9.3 并查集在贪婪算法中的应用
并查集常用于图中的连通性维护，尤其是 Kruskal 算法中判断加边是否成环。它通过快速合并集合与查询集合代表元，帮助算法保持结构合法。
这种数据结构与贪婪选择配合紧密：边按权重排序后，是否加入不仅取决于其代价，还取决于它是否破坏森林结构。
9.4 实现中的边界情况处理
贪婪算法的实现中，边界条件同样重要。例如候选集合为空、存在重复元素、输入规模极小、或多个候选并列最优时，都需要明确处理规则。
若忽视这些细节，算法可能在特定输入下出错。工程上通常要在初始化、循环结束和异常情况上都做完整检查。
10 相关概念
10.1 形式科学中的算法观
在形式科学的视角下，算法不仅是求解工具，也是对问题结构的一种抽象表达。贪婪算法体现了“基于局部信息进行规则化决策”的思想。
它反映出一种重要的算法观：并非所有问题都需要穷举或复杂状态搜索，有些问题可以通过结构性洞察直接压缩求解过程。
10.2 优化问题
贪婪算法最常见于优化问题，即在一组可行方案中寻找代价最小或收益最大的解。其关键不在于“能不能做”，而在于“怎样做得更好”。
在此类问题里，贪婪法常作为一种高效策略，与精确算法、近似算法共同构成求解体系的一部分。
10.3 近似算法
当最优求解过于昂贵时，贪婪算法常可作为近似算法的基础。虽然结果未必绝对最优，但往往足够接近，并且具有较好的时间性能。
某些经典近似算法甚至直接建立在贪婪策略之上，再通过额外分析给出误差界或性能保证。
10.4 组合优化
组合优化研究的是在离散结构中寻找最优配置的问题，例如选边、排程、匹配、覆盖等。贪婪算法与这一领域关系密切，因为许多组合问题都可通过局部选择逐步构造解。
不过，组合优化问题的难点也恰恰在于：并非所有局部最优都能组合成全局最优。贪婪算法因此既是重要工具，也是检验问题结构是否“可贪婪”的方法。