algorithm - 如何发现 "greedy"算法？

Question

我正在阅读 tutorial关于“贪婪”算法，但我很难发现它们解决了真正的“顶级编码器”问题。

如果我知道给定的问题可以用“贪心”算法解决，那么编写解决方案的代码就很容易了。然而，如果我没有被告知这个问题是“贪婪的”，我就无法发现它。

用“贪心”算法解决的问题的共同属性和模式是什么？我可以将它们简化为已知的“贪婪”问题之一(例如 MST)吗？

Answer 1

形式上，您当然必须证明拟阵性质。但是，我假设就顶级编码器而言，您宁愿快速找出是否可以贪婪地解决问题。

在那种情况下，最重要的一点是 optimal sub-structure property .为此，您必须能够发现问题可以分解为子问题，并且它们的最优解是整个问题最优解的一部分。

当然，贪心问题种类繁多，几乎不可能为您的问题提供一个普遍的正确答案。因此，我最好的建议是按照以下思路思考:

• 有时我可以在不同的备选方案之间做出选择吗？
• 这个选择是否会导致可以单独解决的子问题？
• 我能否使用子问题的解决方案推导出整个问题的解决方案？

再加上大量的经验(也不得不这么说)，这应该可以帮助您快速发现贪心问题。当然，您最终可能会将问题归类为贪心问题，但事实并非如此。在那种情况下，您只能希望在编写代码太久之前实现它。

(同样，作为引用，我假设一个顶级编码器上下文......对于任何更现实和实际的结果，我强烈建议在选择贪婪算法之前实际验证拟阵结构。)