我遇到了这个问题 - 在一个无向图中，每个节点和边都有一个权重 . 所有权重都是非负的 . 给定值S，找到具有最小边权重和的连通子图，使得其节点权重之和至少为S.
最明显的解决方案是考虑所有可能的子图的蛮力方法 . 但时间复杂性是指数级的 . 有没有更好的算法呢？我的直觉是我们可以将节点权重转换为边权重，然后应用生成树算法 . 但我无法清楚地解决它 . 如何解决这个问题呢？
编辑：看起来我对子图的描述不够清楚 . 选定的子图必须是单个连接的组件 . 我希望现在很清楚 .
我认为通过减少Steiner树问题，这个问题是NP难的 . 给定图G和需要跨越的一组节点S，将S中所有节点的权重设置为1，将所有其他节点的权重设置为0.节点权重至少为| S |的子图 . 最小总边缘成本必须是树（如果有任何周期，从循环中删除边缘只会降低成本）并且必须连接所有需要跨越的节点 . 因此它是施泰纳树 . 总的来说，这种减少可以用多项式时间计算，所以你的问题是NP难的 .
1 回答
我认为通过减少Steiner树问题，这个问题是NP难的 . 给定图G和需要跨越的一组节点S，将S中所有节点的权重设置为1，将所有其他节点的权重设置为0.节点权重至少为| S |的子图 . 最小总边缘成本必须是树（如果有任何周期，从循环中删除边缘只会降低成本）并且必须连接所有需要跨越的节点 . 因此它是施泰纳树 . 总的来说，这种减少可以用多项式时间计算，所以你的问题是NP难的 .