寻找无向加权图中最小瞭望塔部署子集的算法

这个问题本质上是经典的**集合覆盖问题（Set Cover Problem）**的具体实例，咱们一步步拆解怎么用对应算法解决它：
首先明确核心需求：找最少数量的军事基地，使得每个基地要么被选中部署瞭望塔，要么与某个选中基地的距离≤15英里（瞭望塔覆盖范围）。对应到集合覆盖的定义：

• 全集U是所有军事基地的集合
• 每个基地对应一个子集S_i，S_i包含所有与该基地距离≤15英里的基地（即该基地部署瞭望塔后能覆盖的所有点）
• 我们要找最少数量的S_i，让它们的并集等于U

接下来根据你的基地规模，选择不同的算法方案：

一、精确解法（适合基地数量较少的场景） #

如果基地总数不多（比如≤20个），可以用精确算法找到绝对最优解：

• 回溯法：从最小的可能数量开始尝试验证。比如先检查是否存在单个基地的覆盖集合包含所有基地（也就是有没有一个基地到其他所有基地的距离都≤15）；如果没有，就遍历所有两两组合，看它们的覆盖集合的并集是否覆盖全部基地；以此类推，直到找到满足条件的最小子集。这种方法虽然偏暴力，但小规模场景下完全可行。
• 分支限界法：在回溯的基础上做优化——每次选择一个基地后，计算还剩下多少未覆盖的基地，估算最少还需要多少个基地才能覆盖它们（比如剩下k个未覆盖点，每个基地最多覆盖m个，那至少需要ceil(k/m)个），如果当前已选数量加上这个估算值已经大于当前找到的最优解，就直接剪枝这个分支，避免无效搜索，比纯回溯效率高很多。

二、近似解法（适合基地数量较多的场景） #

集合覆盖是NP-hard问题，大规模场景下找最优解耗时极长，这时候用贪心近似算法是性价比最高的选择，它能在多项式时间内得到一个接近最优的解（理论上不会超过最优解的log(n)倍，n是基地总数），步骤如下：

1. 预处理阶段：为每个基地生成它的覆盖集合——遍历所有基地，计算它到其他基地的距离，把所有距离≤15英里的基地加入这个集合。
2. 初始化状态：已覆盖的基地集合设为空，已选中的瞭望塔集合设为空。
3. 循环选择最优候选：每次从未被选中的基地里，挑出能覆盖最多未被覆盖基地的那个，把它加入选中集合，同时把它覆盖的所有基地标记为已覆盖。
4. 终止循环：当所有基地都被覆盖时，停止循环，此时选中的集合就是我们要的最少瞭望塔部署方案。

额外细节提醒 #

因为你的图是无向加权图，两个基地之间的距离直接用边的权重即可，不需要额外计算（比如平面坐标的欧几里得距离公式在这里用不上，题目已经给出了边的距离权重）。

内容的提问来源于stack exchange，提问作者Sinsinful