如何发现“贪婪”的人算法？ [英] How to spot a "greedy" algorithm?

问题描述

我正在阅读教程关于贪婪算法，但我很难找到解决真正的顶级编码器问题的方法。

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.

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

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)?

推荐答案

形式上，您当然必须证明拟阵属性。但是，我认为就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.

（同样，作为参考，我假设使用topcoder上下文。.出于更现实和实际结果的考虑，我强烈建议在选择贪婪算法之前实际验证拟阵结构。 ）

(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.)

这篇关于如何发现“贪婪”的人算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！