一种证明不存在获得最优解的贪心算法的方法？

Question

问题很简单。我需要证明没有贪婪算法可以为给定问题获得最优解。

我不清楚是否有任何问题必须满足的条件才能存在某种贪心算法以获得最优解。或者，如果存在贪婪算法无法解决问题的任何充分条件。

我说的正是贪色：

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

Answer 1

I need to prove that there's no greedy algorithm that can obtain the optimal solution for a given problem.

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

查看有关图形着色问题的示例，并假设您有一个 oracle M 给出了部分着色的图形，returns 当且仅当存在图形着色时为真它。

现在，使用这个oracle，一个贪心算法可以如下：

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 的最佳答案并将其分配给每个顶点和颜色，其中一组答案为假或真）

有没有出轨的感觉？可能是因为在多项式时间内没有已知的 M 运行s，但是如果你运行一个创建 M 的指数算法，那么肯定有一个贪心算法它。

然而，您可以证明没有已知算法可以在多项式时间内贪婪地选择（或与此相关的任何其他多项式算法）产生图形着色的最佳答案，因为图形着色是 NP 完全的，我们不知道有什么算法可以有效地解决 NPC 问题（而且大多数人认为这样的算法不存在）。

然而，如果在某个时候我们将证明 P=NP，我们可以高效地计算 M，我们将得到一个解决图形着色的高效贪心算法。

Answer 2

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

一种证明不存在获得最优解的贪心算法的方法？

A way to prove that there's no greedy algorithm that obtains optimal solution?

algorithm

greedy