我已经在 Google 和 Stack Overflow 上搜索了我的问题的答案，但我找不到。
我需要找到一个城市电力网络的最佳分布。城市由连通图表示。我想在其中一些节点之间分配发电厂，以覆盖电网中的所有节点。问题在于每个发电厂都有一定的“范围”（例如，它只能覆盖两个节点的“半径”）。我的程序需要找到覆盖整个城市的最少数量的发电厂及其位置。
我从搜索中知道它应该与 MST（最小生成树）有关，但问题出在发电厂的有限范围内。
我考虑过遍历城市中的每个节点并计算包含该节点中发电厂范围内所有节点的子图，直到找到覆盖最多未覆盖节点的子图，然后继续这样做直到整个city 被覆盖（基本上是暴力破解问题），但这似乎非常不切实际，我想知道是否有其他更有效的方法来解决这个问题。
谢谢。
不幸的是，通过从支配集问题的减少，这个问题被认为是 NP 难的。
给定一个图 G，G 中的支配集是一组节点 D，使得图中的每个节点要么在 D 中，要么离 D 有一跳。在图中找到最小支配集的问题已知为NP-hard，这个问题很容易归结为你要解决的问题：给定一个图 G，生成一个与 G 具有相同结构的城市（表示为一个图），然后给每个发电厂的半径为 1 （意味着它可以覆盖一个节点及其所有邻居）。找到覆盖整个城市的最小发电厂集，然后最终为该图生成一个支配集。因此，您的问题是 NP 难的。
正如Wikipedia page 的这一部分中所提到的，事实证明这个问题非常难以近似。维基百科页面列出了一些近似它的算法和方法，但它似乎是那些抵制多项式时间近似方案的 NP 难题之一。
希望这可以帮助！