11

大多数时候，令人困惑的事实是是采用详尽的搜索（动态编程或回溯或蛮力）来解决问题还是采用贪婪的方法。

我不是在谈论使用贪心算法来确定可能的最佳解决方案，而是在谈论使用贪心算法来找到“解决方案”。我正在尝试获得一些标准方法来验证问题是否可以通过贪婪的方法解决。像最优子结构，动态规划的记忆。并且不涉及任何具体问题。

是否有任何归纳证明我可以确定贪婪方法是否总是能产生最佳解决方案？

4

1 回答 1

28

一般来说

为了证明一个优化问题可以使用贪心算法来解决，我们需要证明这个问题有以下几点：

  • 最优子结构性质：最优全局解包含其所有子问题的最优解。

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

例子

让我们考虑经典的活动选择问题。我们有一组N个活动，每个活动都有一个开始时间和s[i]一个结束时间e[i]。我们想选择 S 的一个子集，使得选择最大化非重叠事件的数量。

这个问题可以使用贪心算法来解决，但是我们如何证明呢？

我们需要展示它的展品：

  • 最优子结构

考虑包含在全局最优解 中的一般活动aS = {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最先结束的活动。

  1. 如果b = x，则b位于X的最优解中B，并且我们已经证明贪婪选择包含在最优解中。

  2. 如果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的特定组合结构。

  • 一些聪明人在过去证明了这些拟阵具有最优子结构性质和贪婪选择性质。

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

可以在此处找到有关此的更多信息。

于 2012-07-17T23:25:09.470 回答