如何发现“贪婪”算法？

Question

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

如果我知道可以用“贪婪”算法来解决给定的问题，那么编写解决方案相当容易。但是，如果我没有被告知这个问题是“贪婪的”，我就无法发现它。

“贪婪”算法解决问题的常见属性和模式是什么？我可以将它们减少到已知的“贪婪”问题之一（例如MST）吗？

Answer 1

形式上，你必须证明matroid属性当然。但是，我认为就topcoder而言，您更希望快速了解是否可以贪婪地接近问题。

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

当然，贪婪的问题有如此多种类，以至于无法为您的问题提供一个普通的正确答案。因此，我最好的建议就是沿着这些方向思考：

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

加上负载和负载的经验（不得不这样说），这应该会帮助你快速发现贪婪的问题。当然，你最终可能会将问题归类为贪婪，而事实并非如此。在这种情况下，您只能希望在编码太久之前才能实现它。

（同样，仅供参考，我承担了TopCoder的背景下..什么更多的现实和实际后果的。我强烈建议选择一个贪心算法之前实际验证拟阵结构。）

Answer 2

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

例如，对于bin装箱问题，有几种贪婪算法都比复杂指数算法复杂得多，但您只能确定您会得到一个低于某个阈值比较的解决方案到最佳解决方案。

只有关于贪婪算法会导致最佳解决方案的问题，我的猜测是，归纳正确性证明感觉完全自然和容易。对于你的每一个贪婪的步骤，很明显这是最好的。

无论如何，通常优化和贪婪解决方案的问题很容易，而其他问题则会因为复杂性的限制而迫使您提出一种贪婪的启发式方法。通常有意义的减少会表明你的问题实际上至少是NP难度，因此你知道你必须找到启发式的方法。对于这些问题，我非常喜欢尝试。实施你的算法，并试着找出解决方案是否“非常好”（理想情况下，如果你也有一个缓慢而正确的算法，你可以比较结果，否则你可能需要手动创建实际情况）。只有你有一些行之有效的方法，试着去思考为什么，甚至可以尝试拿出界限的证据。也许它有效，也许你会发现边界案件，它不工作，需要改进。

Answer 3

“用来描述算法族的术语大多数算法都试图从某种初始配置中获得一些”良好“的配置，这只是合法的举动，通常有一些解决方案的”优点“被发现） 贪婪算法总是试图执行它可以执行的最佳合法移动，注意这个标准是局部的：贪婪算法不会“提前思考”，同意现在执行一些平庸的移动，这将允许后来好棋。

例如，对于古埃及分数贪心算法试图找到小分母表示，与其找一个代表，其中最后分母小，它需要在每一步的最小合法书房ominator。一般来说，这在后面的步骤中会导致非常大的分母。

贪婪算法的主要优点通常是简单的分析。编程通常也很容易。不幸的是，它往往是次优的。“ --- ariels （http://www.everything2.com/title/greedy+algorithm?searchy=search）