最少圆问题
有同学提出了这么个问题:在平面上给定n点的坐标(xi,yi)和一个圆的半径r,求至少需要多少个圆可以把所有点覆盖住。
初步的思路是动态规划。
边界条件:n=1,一个圆可以覆盖,此圆以这点为圆心,r为半径。
已知n个点的最少圆,以及每个圆的圆心(每个圆的半径都是r)。现加入第n+1个点。有这么几种情况:
1. 第n+1个点被前面的圆包含,则圆的个数和位置都变;
2. 第n+1个点不被前面的任何圆包含,又分为两种情况
2.1 通过改变某个(些)圆的位置,可以包含此节点,则圆的个数不变,但位置变化;
2.2 如果第二步不能实现,则增加一个以此节点为圆心的圆。
这里主要是第2.1步有点难度,还没有考虑清楚。大家可以广思集益。