如何识别“贪心算法”？

Question

我正在阅读一篇关于“贪心算法”的教程，但是我很难发现它们如何解决真正的“Top Coder”问题。

如果我知道一个给定的问题可以用“贪心”算法来解决，那么编写解决方案就很容易。然而，如果没有告诉我这个问题是“贪心”的，我就无法识别它。

哪些常见属性和模式被贪心算法解决？我能否将它们归结为已知的一个“贪心”问题（例如MST）？

- Michael

Answer 1

正式地说，你当然需要证明 matroid 属性。然而，在 topcoder 中，我认为你更想快速确定问题是否可以贪心地解决。

在这种情况下，最重要的是 最优子结构性质。为此，您必须能够发现问题可以分解成子问题，并且它们的最优解是整个问题的最优解的一部分。

当然，贪心算法问题有如此之多，几乎不可能对您的问题提供一个通用且正确的答案。因此，我的最佳建议是沿着以下方向思考：

• 在某些时候，我是否可以在不同的选择之间进行选择？
• 这个选择会导致可以单独解决的子问题吗？
• 我将能够使用子问题的解决方案来推导出整个问题的解决方案吗？

加上大量的经验（只是这么说而已），这应该可以帮助您快速发现贪心问题。当然，您可能最终将问题分类为贪心问题，但实际上不是。在这种情况下，您只能希望在编写过长时间的代码之前意识到它。

（再次说明，我假设这是 topcoder 上下文。对于任何更现实且具有实际后果的情况，我强烈建议在选择贪心算法之前实际验证 matroid 结构。）

- Frank

---

我认为你指的是“拟阵性质”，而不是“幺半群性质”。另外，你能否更具体地说明“最优子结构”属性？我知道这个属性来自于动态规划，其中你将问题分解成几个子问题，然后重新组合它们。然而，例如在最小生成树中，我很难看出有什么相似之处，因为算法总是只是将前一个解添加到当前解中。 - LiKao

当然，你是正确的，我在这里指的是 matroid。如果你将问题看作是删除边并将剩余图连接到已包含顶点集，则可以看到 MST 的子结构。 - Frank

Answer 2

你的问题有一部分可能是由于思考“贪心问题”引起的。有贪心算法和存在贪心算法导致最优解的问题。还有其他难题也可以通过贪心算法来解决，但结果不一定是最优的。

例如，对于装箱问题，有几种贪心算法，它们的复杂度比指数算法要好得多，但你只能确保得到一个比最优解低一定阈值的解。

仅针对贪心算法会导致最优解的问题，我的猜测是归纳正确性证明感觉非常自然和容易。对于每一个贪心步骤，很明显这是最好的选择。

通常具有最优、贪心解的问题本身就很简单，而其他问题则会迫使你想出贪心启发式，因为复杂性限制。通常，有意义的缩减将表明你的问题实际上至少是NP-hard，并且因此知道你必须找到一种启发式。对于这些问题，我是尝试的忠实拥护者。实现你的算法并尝试找出解是否“相当好”（如果你还有一个慢但正确的算法可与之比较结果，那么最理想，否则你可能需要手动创建基准数据）。只有当你有了一个表现良好的东西，才尝试思考为什么，并可能甚至尝试提出边界证明。也许它能工作，也许你会发现边界情况不起作用，需要改进。

- b.buchhold

Answer 3

“贪心算法”是用来描述一类算法的术语。大多数算法都试图从某个初始状态出发，通过合法的移动达到某种“好”的状态。通常会有一个衡量解决方案优劣的标准（假设找到了解决方案）。

贪心算法总是尝试执行最佳的合法移动。需要注意的是，这个标准是局部的：贪心算法不会“向前思考”，同意执行现在看起来一般般的移动，以便之后能够更好地移动。

例如，埃及分数的贪心算法试图找到一个具有小分母的表示方法。它不是寻找最后一个分母很小的表示方法，而是在每一步中选择最小的合法分母。一般来说，这会导致后面的分母非常大。

贪心算法的主要优点通常是简单易懂。编程也非常容易。不幸的是，它经常是次优的。

- leizisdu