algorithm - 城市中电厂的最优分布

Question

我在 Google 和 Stack Overflow 上都搜索过我的问题的答案，但找不到。

我需要找到城市电力网络的最优分布。城市由连接图表示。我想在其中一些节点之间分布发电厂，以便覆盖电网中的所有节点。问题是每个发电厂都有一定的“范围”(例如它只能覆盖两个节点的“半径”)。我的程序需要找到覆盖整个城市的最少发电厂数量及其位置。

根据我的搜索，我知道它应该与 MST(最小生成树)有关，但问题是在发电厂的有限范围内。

我想过遍历城市中的每个节点，并计算包含该节点中发电厂范围内所有节点的子图，直到找到覆盖最多未覆盖节点的子图，然后继续这样做直到整个城市都被覆盖(基本上是暴力破解问题)，但这似乎很不切实际，我想知道是否还有其他更有效的方法来解决这个问题。

谢谢。

Answer 1

不幸的是，通过从 dominating set 归约，这个问题被认为是 NP 难的问题。

给定一个图 G，G 中的支配集是节点 D 的集合，使得图中的每个节点要么在 D 中，要么距离 D 一跳。在图中找到最小支配集的问题是已知是 NP-hard，这个问题很容易简化为您要解决的问题:给定图 G，生成一个与 G 具有相同结构的城市(表示为图)，然后给每个发电厂一个半径为 1(意味着它可以覆盖一个节点及其所有邻居)。找到覆盖整个城市的最小发电厂集，然后最终为该图生成一个主导集。因此，您的问题是 NP-hard。

如 this section of the Wikipedia page 中所述, 事实证明这个问题出奇地难以近似。维基百科页面列出了一些对其进行近似的算法和方法，但它似乎是那些抵制多项式时间近似方案的 NP 难问题之一。

希望这对您有所帮助!