從傳感器節點到所有其他節點的距離的最小總和

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不被頂點覆蓋，這將是一個矛盾。）