我有一个带有加权边和加权顶点的双向图。我想找到 N 组不相交、相连的顶点，以便:
- 各组权重之和接近但不大于某个值TargetWeight
- 组成这些组的所选边的权重尽可能低。这里有一个问题:如果还选择了另一条边，则边的权重可能会降低(一部分权重在边之间共享)。一个例子:边 E1 的权重为 20，边 E2 的权重为 30，它们共享权重 5。仅取 E1 将导致权重 20，同时使用 E1 和 E2 将导致合并权重为 45(共享权重仅取考虑一次)。
N 是预先知道的，但如果结果会大大改善，则允许更大。
TargetWeight 是预先知道的，当多个低成本的小组优于高成本的大组时，没有可用的实际指标。
在典型情况下，该图有大约 50k 个节点。该图未存储在数据库中。
您可以将此问题视为聚类算法，但关于聚类的一般讨论可能与我需要的有很大不同。我尝试了 KMeans 算法，但我发现结果不够好。现在我正在使用一种基于探索的启发式方法来检查某个选择对 future 群体选择的影响程度。这种方法有效，但速度很慢。
最佳答案
我认为处理这类问题最好的办法是:
首先:定义一个成本函数基于 你是 2 个标准:
Cost(graph) = SUM(Distance(subgraphweight,TargetWeight)) + SUM(WeightEdges(subgraph)) 其中，如果 x>y 则 distance(x,y) 非常大，否则等于 y-x
第二:随机划分图 分成 N(或更多)组不相交的 子图
第三步:遍历图形并从一个顶点移动一个顶点 分组到另一个并检查是否 总成本会降低
关于algorithm - 将加权图划分为同等权重的组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6593599/