我有几个随机分布在二维 map 上的点。我还想放置有限数量的圆圈,以便它们覆盖尽可能多的点,有点像将炮塔放置在基地中以保护有值(value)的建筑物的炮塔游戏 AI。有什么好的方法吗?
最佳答案
您所描述的听起来像是 maximum coverage problem 的一种形式.解决此问题的一种简单方法是应用 greedy algorithm .
这意味着您首先绘制第一个圆圈,使其覆盖尽可能大的区域。然后绘制第二个圆圈,使其覆盖尽可能大的区域,依此类推。
关于寻找最佳区域覆盖的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40629343/