这个问题非常简单。我需要证明没有贪心算法可以获得给定问题的最优解。
我不清楚问题是否必须满足某些条件,以便存在某种贪心算法可以获得最优解。或者是否存在某些充分条件,使得该问题无法通过贪心算法解决。
我具体指的是贪心着色算法:
我不清楚问题是否必须满足某些条件,以便存在某种贪心算法可以获得最优解。或者是否存在某些充分条件,使得该问题无法通过贪心算法解决。
我具体指的是贪心着色算法:
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
的指数算法,则绝对有一种贪心算法适用于它。M
,并获得一种有效的贪心算法来解决图着色问题。