城市發電廠的最佳分配

Question

我已經搜索谷歌和堆棧溢出爲我的問題的答案，但我找不到一個。

我需要找到一個城市的電力網絡的最佳分配。城市由連通圖表示。我希望在其中一些節點之間分配發電廠，以覆蓋電網中的所有節點。問題在於每個發電廠都有一定的「範圍」（例如，它只能覆蓋兩個節點的「半徑」）。我的計劃需要找到覆蓋整個城市的最少數量的發電廠及其位置。

我從我的搜索中知道它應該與MST（最小生成樹）有關，但問題在於發電廠的範圍有限。

我想過要經過城市中的每個節點，並計算包含該節點中發電廠範圍內所有節點的子圖，直到找到覆蓋最多未覆蓋節點的節點，然後繼續進行直到整個城市被覆蓋（基本上是蠻橫的強迫問題），但這似乎很不現實，我想知道是否有其他更有效的方法來解決這個問題。

謝謝。

Answer 1

不幸的是，通過減少dominating set問題已知這個問題是NP-hard。

給定一個圖G，G中的一個支配集合是一組節點D，使得圖中的每個節點都在D中或離D一跳。在圖中找到最小支配集的問題已知是NP難題，並且這個問題很容易減少到你想要解決的問題：給定一個圖G，產生一個與G有相同結構的城市（表示爲一個圖），然後給每個發電廠半徑爲1（這意味着它可以覆蓋節點及其所有鄰居）。找到覆蓋整個城市的最小的發電廠組，然後最終產生一個支配圖。因此，你的問題是NP難。

正如在this section of the Wikipedia page中所提到的，事實證明，這個問題出人意料地難以估計。維基百科頁面列出了一些用於近似的算法和方法，但它似乎是抵制多項式時間近似方案的NP難題之一。

希望這會有所幫助！