用于在图中找到最大独立集的算法是否正确？

Question

我们对算法有以下输入:

G没有循环(也称为生成树)的图形,其中每个节点具有相关的权重.

我想找到一个独立的集合S:

• 没有两个元素S形成边缘G
• 没有其他可能的子集满足上述条件,其重量大于S[0] + S[1] + ... + S[n-1] (其中len(S)==n).

这是我到目前为止的高级伪代码:

MaxWeightNodes(SpanningTree S):
    output = {0}
    While(length(S)):
        o = max(node in S)
        output = output (union) o
        S = S \ (o + adjacentNodes(o))
    End While
    Return output   

有人可以告诉我我是否犯了任何错误,或者这个算法会给我我想要的结果吗？

Answer 1

该算法无效,因为您很快就会遇到这样的情况,即排除初始最大值的相邻节点可能是最佳的本地解决方案,但不是最佳的全局决策.

例如,output = []:

        10
      /    \
   100      20
   /  \    /  \
  80  90  10   30

output = [100]:

         x
      /    \
     x      20
   /  \    /  \
  x    x  10   30

output = [100, 30]:

         x
      /    \
     x      x
   /  \    /  \
  x    x  10   x

output = [100, 30, 10]:

         x
      /    \
     x      x
   /  \    /  \
  x    x  x    x

虽然我们知道有更好的解决方案.

这意味着你没有一个贪婪的算法,没有一个最佳的子结构.