algorithm - 确定是否可以使用贪心算法最优地给出解

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center提供指导。




已关闭8年。




大多数时候，令人困惑的事实是是要进行详尽的搜索(动态编程，反向跟踪还是蛮力)以解决问题，还是采用贪婪的方法。

我不是在谈论使用贪婪来确定最佳的解决方案，而是在谈论使用贪婪算法来查找“解决方案”。我正在尝试获得一些标准方法，可以用来验证是否可以使用贪婪方法解决问题。像最优子结构一样，用于动态编程的存储。与无关的任何具体问题。

我可以做些归纳证明来决定贪婪方法是否总能产生最佳解决方案吗？

最佳答案

一般来说
为了证明可以使用贪婪算法来解决优化问题，我们需要证明该问题具有以下几点:

最优子结构属性:最优全局解包含所有子问题的最优解。

贪婪的选择属性:可以通过贪婪地选择局部最优选择来获得全局最优解。

例子

This problem can be solved using a greedy algorithm，但是我们如何证明呢？
我们需要展示它的展品:

最佳子结构

考虑全局最优解S = {A', a, A''}中包含的一般事件a，其中S是全局最优解，a是我们的小事件，而A'和A''是在a之前和之后找到事件的两个子问题。
如果问题具有最佳子结构属性，则子问题A'和A''的最佳解决方案必须包含在全局最佳解决方案S 中。
这是真的，但是为什么呢？
假设子问题A'的最佳解决方案不在S中。然后我们可以用A'中的S'代替A的最优值，以获得比S更好的新的全局最优解。但是S是全局最佳解决方案!矛盾。

贪婪的选择:

我们需要证明我们的贪婪选择(选择最先结束的事件)是正确的。
令B为一个子问题。令b为第一个结束的子问题B的事件，因此b是我们的(第一个)贪婪选择。 我们需要证明b包含在B 的某些最佳解决方案中。
令X为子问题B的最佳解决方案。令x为X中最先结束的事件。

如果b = x，则b在X中，这是B的最优解，并且我们已经表明，贪婪的选择包括在最优解中。

如果b!= x，那么我们肯定有end_time[b] < end_time[x]。
由于b是我们的贪婪选择(即首先在子问题B中结束的事件)，因此我们可以用x中的b替换X以获得另一个最佳解决方案:X' = (X \ {x}) U {b}。 X'是最佳的，因为它具有与X相同的事件数，并且X是最佳的，并且在这种情况下，b在X'中，这是B的最佳解决方案。

因此，在一种情况或另一种情况下，我们对b的最佳选择中都包含了我们的贪婪选择B。

拟阵
此外，有一个强大的数学理论可以用表示，在某些情况下可以机械地证明可以用贪婪的方法解决特定问题。
简要地:

可以定义一种名为 matroid 的特定组合结构。

过去有个聪明人证明，这些类机器人具有最优子结构属性和贪婪选择属性。

这意味着您可以对优化问题运行贪婪算法，并且它将找到最佳解决方案。您只需要来验证您的问题是在类拟阵结构上定义的。

有关此的更多信息，请参见here。