导弹杀伤半径内覆盖最多敌人的最优起爆坐标求解问题

问题通用名称 #

这个问题的通用名称是最大覆盖圆问题（Maximum Coverage Circle Problem），特指平面上固定半径的圆覆盖最多点的优化问题。

是否属于组合问题 #

是的，它属于组合优化问题。虽然圆心的位置看似是连续的二维空间，但最优解的候选集合可被离散化为有限个点，本质是从这些有限候选中挑选最优解，符合组合问题的核心特征。

多项式时间算法是否存在 #

存在多项式时间算法，核心思路如下：

• 最优起爆圆心的候选位置仅包含三类：
  1. 某个敌人的坐标点：以该点为圆心，覆盖所有距离它≤r的敌人；
  2. 两个敌人坐标连线中垂线上的点：要求该点到这两个敌人的距离均为r（仅当两点间距≤2r时存在）；
  3. 三个敌人的外接圆圆心：要求该外接圆的半径恰好等于r（仅当存在这样的外接圆时有效）。
• 候选圆心的总数为O(n²)级别（n为敌人数量），对每个候选圆心，遍历所有敌人计算距离是否≤r以统计覆盖数量，最终取覆盖数最大的圆心即可。
• 整个算法的时间复杂度为O(n²)，属于多项式时间范畴。

补充说明 #

你提到的质心思路失效的情况很典型：当敌人分散为多个远距集群时，质心往往落在集群间的空白区域，无法有效覆盖任何集群。而上述算法通过枚举所有关键候选点，能确保找到真正的最优解。

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