问题
问题描述
假设海岸线是一条无限延伸的直线，陆地在海岸线的一侧，海洋在另外一侧。每个小岛相当于海洋侧的一个点。坐落在海岸线上的基站只能覆盖半径为d的范围。应用直角坐标系，将海岸线作为x轴，设海洋侧在x轴上方。给定海洋中各小岛的位置，以及通信基站的覆盖半径，要求用最少的基站覆盖所有小岛，使得每个小岛都能和陆地通过某基站通信（在某个基站覆盖范围内）。
问题形式化定义
输入
- S = {S1,S2,...,Sn}，半径d
输出
- P = {P1,P2,...}
算法描述
贪心思想
简单来讲，就是在对于Si画圆，要求圆心在x轴上，且圆心应当处于Si右侧，以及Si在该圆上。我们所要关心的是圆与x轴的左交点的横坐标。
依据左交点横坐标的大小，对S集合中的点进行升序排列。依次处理排序后最前端的点Si，如果P中不存在圆容纳Si，那么将Si之前所画圆的圆心容纳入集合P中，否则，继续处理下一个点。
举例为：
如上图，输入小岛坐标S=[S2,S1,S4,S3]，按照以各点为圆上一点时，该圆与x轴的左交点左至右（从小到大）排序后得到S=[S1,S2,S3,S4]。
开始作圆，从左至右，从S1开始，即先画出黄圈，到S2，因为S2在上一圆内，故继续；到S3，因S3在上一圆（黄圈）外，故保留上一圆（黄圈），另作新圆（蓝圈），到S4，因S4在上一圆（蓝圈）内，故继续。
否则，如果只是按照x坐标从左至右排序，即从S2开始作圆，到S1，S1并不在S2所作的红圈内，故作新圆，如此产生多余的圆。
分析贪心选择性
定理， 存在一个原问题的最优解P，P点一定包含上述排序之后最前端点S0所画圆的圆心y。
证明， 如果不存在这样的最优解，包含S0所画圆的圆心y。那么对于该问题的任意一个最优解M而言，其一定存在一个圆心x，使得以x为圆心的点包含点S0。令N = (M/{x})U{y}，N同样是原问题的解。以y为圆心的圆一定可以包含仅由x为圆心的圆所包含的点（这一点是显然的，也是无法证明的）。所以，|M|=|N|，M同样是原问题的一个最优解，这与假设矛盾，所以假设不成立。
分析优化子结构
定理， 对于原问题的包含上述排序之后最前端点S0所画圆的圆心y的最优解P而言，P/{y}是 S/{a|a∈P,且a包含在以y为圆心的圆内}的该问题的最优解。
证明， P/{y}不是 S/{a|a∈P,且a包含在以y为圆心的圆内}的该问题的最优解，那么一定存在该问题的一个最优解D，|D|<|P/{y}|+1，这与P是原问题的最优解矛盾，假设不成立。,那么，DU{y}一定是原问题的一个解，而|DU{y}|=|D|+ 1 > |P|=|P/{y}|+1，这与P是原问题的最优解矛盾，假设不成立。
算法设计
Seclet-circle(P[1..n],d);
ascending sort P by p.x + sqrt(d*d - p.y*p.y) - d;
S = null;
vertex = null;
for i=0 to n do
if S == null || dis(P[i],vertex) > d
vertex = {P[i]所画圆的圆心};
S = SU{vertex};
return S;
算法复杂性分析
O(nlogn) + O(n) = O(n).
本文引用自文章 最少圆覆盖通信覆盖问题-算法分析设计-贪心算法-java实现