algorithm - 这个在图中寻找最大独立集的算法是否正确？

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

输出 = [100]:

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

输出 = [100, 30]:

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

输出 = [100, 30, 10]:

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

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

这意味着您使用的是贪心算法，没有 optimal substructure .