22

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

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

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

4

3 回答 3

15

Formally, you'd have to prove the matroid property of course. However, I assume that in terms of topcoder you rather want to find out quickly if a problem can be approached greedily or not.

In that case, the most important point is the optimal sub-structure property. For this, you have to be able to spot that the problem can be decomposed into sub-problems and that their optimal solution is part of the optimal solution of the whole problem.

Of course, greedy problems come in such a wide variety that it's next to impossible to offer a general correct answer to your question. My best advice would hence be to think somewhere along these lines:

  • Do I have a choice between different alternatives at some point?
  • Does this choice result in sub-problems that can be solved individually?
  • Will I be able to use the solution of the sub-problem to derive a solution for the overall problem?

Together with loads and loads of experience (just had to say that, too) this should help you to quickly spot greedy problems. Of course, you may eventually classify a problem as greedy, which is not. In that case, you can only hope to realize it before working on the code for too long.

(Again, for reference, I assume a topcoder context.. for anything more realistic and of practical consequence I strongly advise to actually verify the matroid structure before selecting a greedy algorithm.)

于 2011-10-25T10:01:06.193 回答
5

您的问题的一部分可能是由“贪婪问题”的想法引起的。有贪心算法和问题，有贪心算法会导致最优解。贪心算法也可以解决其他难题，但结果不一定是最优的。

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

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

通常，最优、贪心解决方案的问题很容易解决，而由于复杂性限制，其他问题会迫使您提出贪心启发式方法。通常，有意义的减少将表明您的问题实际上至少是 NP 难的，因此您知道您必须找到一个启发式方法。对于这些问题，我非常喜欢尝试。实现您的算法并尝试找出解决方案是否“相当好”（如果您也有一个缓慢但正确的算法，您可以比较结果，否则您可能需要手动创建基本事实）。只有当你有一些运作良好的东西时，试着想想为什么，甚至尝试提出边界证明。也许它有效，也许你会发现它不起作用并需要改进的边界情况。

于 2011-10-25T10:56:28.713 回答
0

“用于描述一系列算法的术语。大多数算法试图从一些初始配置达到一些“好”配置，只采取合法的行动。通常有一些解决方案的“好”程度（假设找到一个）。贪婪算法总是尝试执行它所能做的最好的合法移动。注意这个标准是局部的：贪婪算法不会“提前考虑”，同意现在执行一些看起来平庸的移动，这将允许以后更好的移动。

例如，埃及分数的贪心算法试图找到具有小分母的表示。它不是寻找最后一个分母很小的表示，而是在每一步都取最小的合法分母。通常，这会导致后续步骤的分母非常大。

贪心算法的主要优点通常是分析简单。它通常也很容易编程。不幸的是，它通常不是最理想的。” --- ariels (http://www.everything2.com/title/greedy+algorithm?searchy=search)

于 2011-12-06T14:39:10.243 回答