该算法用于在图中找到最大独立集正确吗？

没有周期（又名生成树）的图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

有人能告诉我，蝙蝠是否我做了任何错误，或者如果该算法给我，结果我想？

来源

2013-03-25 Govind Parmar

为什么不尝试实施它来证明算法的正确性？ – TravellingGeek 2013-03-25 04:05:33

@GeraldSv随着问题的增加，通常最好的解决方案是在任何实现之前证明算法是有效的。花几个星期/几个月的时间去实施一些事情，找出一个简单的角落案例可能已经被识别出来，会让人很难过 - 不会花费我太多时间，但我已经遇到过这样的问题*（： – Rubens 2013-03-25 04:14:54

@GeraldSv You不要执行算法来证明它们的正确性，你可以正式做到这一点。否则，建议对我不好。 – 2013-03-25 05:33:52

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

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

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

这意味着你陷入贪婪的算法，没有optimal substructure。

来源

2013-03-25 04:07:00 Rubens

我认为顶点的权重使得贪婪的解决方案变得困难。如果所有的权重相等，你可以尝试选择一组树的层次（这对于完整的k-tree树来说显然是最简单的，但是生成树通常不属于该类）。也许这对贪婪近似很有用，因为你可以选择树的同一级别的所有顶点（独立于你所在的顶点）来进入相同的独立组;在同一级别的两个顶点之间不能有边缘。我没有提供解决方案，因为这对我来说似乎是一个难题。主要的问题似乎是权重和事实，你不能假定你正在处理完整的树木。

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

来源

2013-03-25 05:44:12

该算法用于在图中找到最大独立集正确吗？

回答

相关问题