2

我们有以下算法输入：

一个G没有循环的图（又名生成树），其中每个节点都有一个相关的权重。

我想找到一个独立的集合S，这样：

  • 没有两个元素S形成边G
  • 没有其他可能的子集满足上述条件，其权重大于S[0] + S[1] + ... + S[n-1] (where 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

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

4

2 回答 2

5

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

例如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

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

这意味着您使用贪心算法，没有最佳子结构。

于 2013-03-25T04:07:00.010 回答
2

我认为顶点的权重使贪婪的解决方案变得困难。如果所有权重都相等，您可以尝试选择树的一组级别（这显然对于完整的 k-ary 树来说是最简单的，但生成树通常不属于该类）。也许将级别视为具有组合权重的贪婪近似会很有用，因为您始终可以选择树的同一级别的所有顶点（与您根植于哪个顶点无关）进入相同的独立放; 同一级别的两个顶点之间不能有边。我没有提供解决方案，因为这对我来说似乎是一个难题。主要问题似乎是权重以及您不能假设您正在处理完整的树这一事实。

编辑：实际上，总是选择一个级别的所有顶点似乎也是一个坏主意，因为鲁本斯的例子有助于形象化；想象他的树右侧第二层的顶点的权重为 200。

于 2013-03-25T05:44:12.177 回答