我正在寻找一种算法。假设我们有一个带有顶点 {A, B, C, D, E... } 的图，并且每个顶点可能有多个加权边到集合中的其他顶点(我将构成一个邻接列表作为示例):
A: (B, 34), (C, 32), (E, 20)
B: (A, 30)
C: (C, 32), (D, 41)
D: (B, 34), (A, 30), (E, 20)
E: (D, 41)
同一节点的边总是具有相同的值。
我想找到边权重总和最大的子集(某个固定长度的子集)，其中到节点的边只计算一次。换句话说，在此示例中，长度为 2 的最大子集是 {C, D}，值为 30 + 34 + 32 + 41 + 20 = 157(它命中所有值)。尽管 A 具有最大的个体值，但它不包含在这个总和中，并且将它与任何其他节点相加并没有达到所有值。
为清楚起见，{C, E} 的子集为 32 + 41 = 73(到 D 的边未计算两次)。
通过蛮力执行此操作类似于 O(V!*lg(V))，因为最后会找到组合和排序。有什么方法可以更有效地计算它吗？
最佳答案
我想我会陈述我到目前为止的想法。我还没有想出任何更好的最坏情况保证，但我想出了一个保证找到最佳解决方案的修剪启发式方法。假设有名为 x 和 y 的集合，每个集合的大小为 n(不过 x 也可以小于 y)。如果 y 是 x 的子集，则可以保证任何用 y 替换 x 的集合至少与使用 y 的集合一样好。检查任何集合是否是超集将花费最坏情况下的二次时间，但如果预期顶点相似(或在合并后相似)，则这可能会导致计算时间减少。
关于algorithm - 查找图的最大子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51757884/