贪心算法

贪心算法通过在每一步选择当前看起来最佳的选项来逐步构建解决方案，并且只有当这种局部最优选择能够被证明导致全局最优解决方案时，它才是正确的。

Definition

贪心算法通过一系列选择来构建解决方案，每个选择都旨在优化某个局部标准，并且从不重新审视之前的选择；它只有在局部最优选择产生全局最优结果时才是正确的。

Scope

本主题涵盖贪心范式：证明其合理性的贪心选择性质和最优子结构，标准证明技术（交换论证和拟阵框架），以及典型的贪心算法，包括霍夫曼编码、最小生成树（Kruskal和Prim）、Dijkstra最短路径和区间调度。它还讨论了贪心策略何时仅作为近似启发式而非精确方法。

Core questions

• 什么是贪心选择性质，以及如何为给定问题证明它？
• 交换论证如何证明贪心选择是安全的？
• 哪些问题具有保证贪心最优性的拟阵结构？
• 贪心方法何时仅是近似算法而非精确算法？
• 贪心算法与动态规划在同一问题上的比较如何？

Key concepts

• 贪心选择性质
• 最优子结构
• 交换论证
• 拟阵
• 霍夫曼编码
• 最小生成树
• 区间调度
• 分数背包

Key theories

贪心选择性质和交换论证

当一个全局最优解总是可以通过修改来与贪心的第一个选择保持一致而不损失最优性时，问题就允许贪心解；交换（或“贪心保持领先”）论证使之形式化。

拟阵和贪心最优性

当可行解构成加权拟阵的独立集时，贪心算法总是能找到最大权独立集；这统一了诸如Kruskal最小生成树算法最优性等结果。

Clinical relevance

贪心算法驱动着广泛使用的系统：数据压缩格式中的霍夫曼编码、网络设计中的最小生成树算法、路由和导航中的Dijkstra算法，以及操作系统和资源分配中的贪心调度和集合覆盖启发式算法。

History

贪心推理出现在经典成果中，例如Kruskal（1956）和Prim（1957）的最小生成树算法、Huffman（1952）的最优前缀码以及Dijkstra（1959）的最短路径算法。关于贪心方法何时成功的拟阵理论解释由Edmonds及其他人在1960年代和1970年代提出。

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

为什么贪心算法适用于分数背包问题而不适用于0/1背包问题？

在分数背包问题中，物品可以被分割，因此首先选择单位价值最高的物品总是安全且可证明最优的。在0/1背包问题中，物品不可分割，贪心选择可能会排除更好的组合，需要动态规划才能获得精确最优解。

如何证明贪心算法是正确的？

两种标准技术是交换论证（将任何最优解转换为贪心解而不使其变差）和“贪心保持领先”论证（表明贪心部分解在每一步都至少与任何其他解一样好）。拟阵理论提供了一个通用的充分条件。