证明没有贪心算法可以获得最优解的方法是什么？

Question

这个问题非常简单。我需要证明没有贪心算法可以获得给定问题的最优解。

我不清楚问题是否必须满足某些条件，以便存在某种贪心算法可以获得最优解。或者是否存在某些充分条件，使得该问题无法通过贪心算法解决。

我具体指的是贪心着色算法：

http://en.wikipedia.org/wiki/Greedy_coloring

- D1X

---

可能是错误的（因此不是答案），我不相信你能证明不存在贪心算法，因为这将取决于贪心性质。然而，对于图着色问题，你可以证明没有已知的贪心算法，因为该问题是NP-完全的，而贪心算法在多项式时间内运行，一次选择一个元素。 - amit

同意。我觉得你真正想知道的是如何证明特定的贪心算法并不总是获得最优解。我甚至不确定贪婪有没有一个正式的定义。 - Juan Lopes

我认为贪心的定义是始终尝试选择局部/当前最佳选项。贪心算法有时可能与非贪心算法一样优秀，但通常不是这样。 - Mateusz Piotrowski

就我所知，对于背包问题，反例是有效的，但我不确定对于图着色问题是否也适用。这个问题讨论了提供一个具体的反例场景，在这种情况下，它不能给出最优解，http://stackoverflow.com/questions/12023731/graph-coloring-and-np-completeness - matrixanomaly

根据我的经验，当优秀的性能比高质量的结果更为重要时，贪心算法非常有用。贪心算法通常执行较少操作（通常在搜索阶段），并返回可能不是最优的结果。我不知道这是否可以被证明。 - Gentian Kasa

Answer 1

我需要证明没有贪心算法可以获得给定问题的最优解。

嗯，这将取决于您选择的属性定义。

例如，看看图着色问题，并假设您有一个名为M的预言机。该预言机会在给定部分着色的图形上返回true，当且仅当它有一个图形着色。

现在，使用此预言机，贪心算法可以如下所示：

for each vertex v:
   for each color c:
        temporarly color v with c
        run M on partially colored graph
        if M yields true, make c constant to v, and abort the inner loop

上述算法是以贪心的方式对图进行着色，每次选择一个顶点，根据预言者 M 的答案进行着色。（选择 M 的最佳答案并将其分配给每个顶点和颜色，其中答案集为 false 或 true）

感觉像作弊吗？可能是这样，因为目前没有已知的 M 可在多项式时间内运行，但如果您运行创建 M 的指数算法，则绝对有一种贪心算法适用于它。

然而，您可以证明，对于图着色问题，不存在已知的能够在多项式时间内贪心选择并得出最优解（或任何其他多项式算法）的算法，因为图着色是 NP-完全问题，并且我们不知道任何可有效解决 NPC 问题的算法（大多数人认为这样的算法不存在）。

然而，如果有一天我们证明了 P=NP，我们就可以有效地计算出 M，并获得一种有效的贪心算法来解决图着色问题。

- amit

Answer 2

贪心算法在哲学层面上是一种现象，当属性持有者考虑短期利益而忽略长期收益时发生。正如我们所见，这不是一个明确定义的概念。那么算法为什么会贪心呢？如果我们不知道其贪婪本质，那么我们就没有办法证明它不能获得最优解。此外，获得最优解的概念也是模糊的。它可能意味着它永远无法获得最优解，也可能意味着至少有一种情况它无法获得最优解。我建议记录这个问题，了解问题，然后开始思考如何再次证明它。

- Lajos Arpad