如何识别“贪婪”的人算法？
我正在阅读关于“贪婪”算法的教程，但是我很难发现他们解决真正的“顶级程序员”问题。
如果我知道给定的问题可以用“贪婪”算法解决，那么编写解决方案就很容易了。然而，如果我没有被告知这个问题是“贪婪的”，我就无法发现它。
用“贪婪”算法解决的问题有哪些共同属性和模式？我可以将它们简化为已知的“贪婪”问题之一（例如 MST）吗？
I am reading a tutorial about "greedy" algorithms but I have a hard time spotting them solving real "Top Coder" problems.
If I know that a given problem can be solved with a "greedy" algorithm it is pretty easy to code the solution. However if I am not told that this problem is "greedy" I can not spot it.
What are the common properties and patterns of the problems solved with "greedy" algorithms? Can I reduce them to one of the known "greedy" problems (e.g. MST)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
形式上，你当然必须证明拟阵性质。然而，我认为就 topcoder 而言，您宁愿快速找出问题是否可以贪婪地解决。
在这种情况下，最重要的一点是最佳子结构属性。为此，您必须能够发现问题可以分解为子问题，并且它们的最优解是整个问题最优解的一部分。
当然，贪婪问题的种类繁多，几乎不可能为您的问题提供普遍的正确答案。因此，我最好的建议是沿着这些思路思考：
加上大量的经验（也不得不说），这应该可以帮助您快速发现贪婪的问题。当然，您最终可能会将问题归类为贪婪问题，但事实并非如此。在这种情况下，您只能希望在长时间处理代码之前意识到这一点。
（再次，作为参考，我假设一个 topcoder 上下文......对于任何更现实和实际的结果，我强烈建议在选择贪婪算法之前实际验证拟阵结构。）
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:
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.)
你的问题有一部分可能是由“贪婪问题”的思维引起的。存在贪婪算法，存在贪婪算法的问题会导致最优解。还有其他难题也可以通过贪心算法来解决，但结果不一定是最优的。
例如，对于装箱问题，有几种贪婪算法，它们的复杂度都比指数算法好得多，但您只能确定与最佳解决方案相比，您将获得低于特定阈值的解决方案。
仅对于贪婪算法将导致最佳解决方案的问题，我的猜测是归纳正确性证明感觉完全自然且简单。对于你每一个贪婪的步骤，很明显这是最好的做法。
通常情况下，具有最优、贪婪解决方案的问题很容易解决，而其他问题则由于复杂性的限制，会迫使您提出贪婪的启发式方法。通常，有意义的减少将表明您的问题实际上至少是 NP 困难的，因此您知道您必须找到启发式方法。对于这些问题，我非常热衷于尝试。实现您的算法并尝试找出解决方案是否“相当好”（理想的情况是您还有一个缓慢但正确的算法，您可以将结果进行比较，否则您可能需要手动创建基本事实）。只有当你有一些效果很好的东西时，才尝试思考为什么，甚至尝试提出边界证明。也许它有效，也许您会发现它不起作用并需要改进的边界情况。
A part of your problem may be caused by thinking of "greedy problems". There are greedy algorithms and problems where there is a greedy algorithm, that leads to an optimal solution. There are other hard problems that can also be solved by greedy algorithms but the result will not necessarily be optimal.
For example, for the bin packing problem, there are several greedy algorithms all of them with much better complexity than the exponential algorithm, but you can only be sure that you'll get a solution that is below a certain threshold compared to the optimal solution.
Only regarding problems where greedy algorithms will lead to an optimal solution, my guess would be that an inductive correctness proof feels totally natural and easy. For every single one of your greedy steps, it is quite clear that this was the best thing to do.
Typically problems with optimal, greedy solutions are easy anyway, and others will force you to come up with a greedy heuristic, because of complexity limitations. Usually a meaningful reduction would be showing that your problem is in fact at least NP-hard and hence you know you'll have to find a heuristic. For those problems, I'm a big fan of trying out. Implement your algorithm and try to find out if solutions are "pretty good" (ideal if you also have a slow but correct algorithm you can compare results against, otherwise you might need manually created ground truths). Only if you have something that works well, try to think why and maybe even try to come up with proof of boundaries. Maybe it works, maybe you'll spot border cases where it doesn't work and needs refinement.
“用于描述一系列算法的术语。大多数算法尝试从某些初始配置达到某些“良好”配置，仅进行合法的移动。通常有某种解决方案“良好”的衡量标准（假设找到了一个）。
贪心算法总是尝试执行其所能执行的最佳合法动作。请注意，这个标准是局部的：贪婪算法不会“提前思考”，同意现在执行一些看起来平庸的动作，这将允许以后更好的动作。
例如，埃及分数的贪婪算法试图找到分母较小的表示。它不是寻找最后一个分母较小的表示，而是在每一步中采用最小的合法分母。一般来说，这会导致后续步骤中的分母非常大。
贪心算法的主要优点通常是分析简单。通常也很容易编程。不幸的是，它通常不是最佳的。”
---艾瑞尔
(http://www.everything2.com/title/greedy+algorithm?searchy=search)
"A term used to describe a family of algorithms. Most algorithms try to reach some "good" configuration from some initial configuration, making only legal moves. There is often some measure of "goodness" of the solution (assuming one is found).
The greedy algorithm always tries to perform the best legal move it can. Note that this criterion is local: the greedy algorithm doesn't "think ahead", agreeing to perform some mediocre-looking move now, which will allow better moves later.
For instance, the greedy algorithm for egyptian fractions is trying to find a representation with small denominators. Instead of looking for a representation where the last denominator is small, it takes at each step the smallest legal denominator. In general, this leads to very large denominators at later steps.
The main advantage of the greedy algorithm is usually simplicity of analysis. It is usually also very easy to program. Unfortunately, it is often sub-optimal."
--- ariels
(http://www.everything2.com/title/greedy+algorithm?searchy=search)