从传感器节点到所有其他节点的距离的最小总和

Question

有没有一种方法可以在中等规模（最多1000个节点）加权图上计算（准确或统计）这个问题？

将n个（例如5个）传感器放置在图的节点中，使得每个其他节点到最近的传感器的距离之和最小。

Answer 1

这种类型的问题被称为图聚类。其中一种常用的解决方法是马尔可夫聚类（MCL）算法。网络搜索应该提供一些实现示例。但它通常不提供最佳解决方案。

Answer 2

我会通过从Vertex Cover中减少来证明这个问题是NP-hard。即使图表未加权（您不会说是否加权）也适用。

给定一个不加权的图G =（V，E）和一个整数k，Vertex Cover问的问题是“是否存在一个至多有k个顶点的集合，使得每个边在这个集合中至少有一个端点？”我们将建立一个新的图G'=（V'，E），它与G相同，除了所有孤立的顶点已经被丢弃，在G'上解决你的问题，然后用它来回答关于顶点覆盖的原始问题。

假设确实存在k个顶点的这样的集合S.如果我们认为这个集合S是将传感器放在问题中的位置，那么S中的每个顶点的距离为0，而其他每个顶点与S中的顶点的距离恰好为1（因为如果有一些顶点u不是真的，这意味着你的邻居都不在S中，所以对于每个这样的邻居，边uv不被顶点覆盖，这将是一个矛盾。）