最大覆盖算法

1. 在计算机科学中，有哪些非常巧妙的算法

分支界定算法（Branch and Bound）——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

动态规划算法（Dynamic Programming）——展示互相覆盖的子问题和最优子架构算法

欧几里得算法（Euclidean algorithm）——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

期望-最大算法（Expectation-maximization algorithm，又名EM-Training）——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值；第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值

2. 求一般图的最大权匹配的算法（最好详细一些，注意数最大权匹配），高分求助！

Algorithmus 3.3 Kruskal's Algorithm 时间复杂度 O(mlog n)
m边数 n点数
输入: 图 G = (V;E) 和 权c : E -》R.
输出: 一棵最优树 T.
begin
把所有边以权的大小按从小到大排序
T := (VG，ET ) := (VG， 空);
for i = 1 to m do
if T + ei 没有圈 then
T := (VG;ET 并上 {ei});
if end
for end
end

或者 Algorithmus 3.5 Prim's Algorithm 时间复杂度O(m+n log n)

3. 构造辅助网络后如何用最大流算法求最小割

在算法中一般存在最大-最小定理。

1 、最大匹配<==>最小覆盖

2、 最大流<==>最小割

最大流-最小割定理理解引自呆欧的形象表达：“多粗的管子，水就最多多大流量”，比如从自来水厂到用水大户工业小区A 能达到的水的最大流量是多大？考虑到可能从水厂到小区有不少到达的水管，那么最大的流量等于拆掉最少最细的水管后水厂不能给小区A 供水的那些水管流量的集合。当然这种说法并不不严谨，因为这里水管不是双向的，而在网络中谈论的信息流却可是是双向的。

其实最大流-最小割最难的地方在于构图了，还有必须掌握Dinic算法。

高效的求最大流算法——Dinci算法：

Dinci算法是基于“层次图”的时间效率优先的最大流算法。

层次：从源点走到终点的最短路长度。层次图：每次从源点到终点距离最短并且记录了多条增广路径（在找到最短路的过程记录了多条增广路径，因为找最短路径的过程中自然有分叉，有分叉那么增广路径条数不就变多了么）。在dfs遍历的时候必须按照层次走。

Dinic算法的思想是为了减少增广次数，建立一个辅助网络L，L与原网络G具有相同的节点数，但边上的容量有所不同，在L上进行增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流

Dinic三步曲：

1、利用原网络构造层次图，顺便判断原网络还有无增广路。

2、利用构造的层次图求此次的最大流，若找不到增广路了则算法结束

3、更新原网络，即增广过程中遇见的边其正边以及逆边的的容量大小。

重复上述的三步。

4. 图论中无向图求解最小覆盖，是通过求最大匹配x，然后用顶点数n-x得到答案

这个DFS是找最大匹配的hungray算法 ，你网络一下就知道了

5. 近似算法的集合覆盖问题的近似算法

问题描述：给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。
集合覆盖问题的一个实例〈X,F〉由一个有限集X及X的一个子集族F组成。子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X= 。对于F中的一个子集CF，若C中的X的子集覆盖了X，即X= ，则称C覆盖了X。集合覆盖问题就是要找出F中覆盖X的最小子集C*，使得
|C*|=min{|C||CF且C覆盖X}
集合覆盖问题举例：用12个黑点表示集合X。F={S1,S2,S3,S4,S5,S6,}，如图所示。容易看出，对于这个例子，最小集合覆盖为：C={S3,S4,S5,}。
集合覆盖问题近似算法——贪心算法
Set greedySetCover (X,F)
{
U=X；
C=；
while (U !=) {
选择F中使|S∩U|最大的子集S；
U=U-S；
C=C∪{S}；
}
return C；
}
算法的循环体最多执行min{|X|，|F|}次。而循环体内的计算显然可在O(|X||F|)时间内完成。因此，算法的计算时间为O(|X||F|min{|X|，|F|})。由此即知，该算法是一个多项式时间算法。

6. 无线传感器网络的覆盖控制算法有哪几类

通常无线传感器网络的节点在目标区域的部署有大规模、高密度的特点，这就导致网络中大量节点的覆盖区域相互交叠。这种覆盖冗余性会导致采集、传输数据的冗余以及信道的干扰，浪费了有限的能量资源。使用合适的覆盖控制算法和节点调度算法在保证一定覆盖性的前提下使一些节点的传感模块策略性的休眠，对延长网络生存时间有重要意义！

7. 下面哪个问题不属于强np难的 最大团 排序 点覆盖

排序不算NP问题吧。你应该见过很多时间复杂度在多项式内的排序算法吧，比如复杂度在O (nlogn)的堆排序等等。
其他两个是典型np hard问题。最大团是maximum independent set，点覆盖是minimum vertex cover。

8. 完全覆盖问题

最大覆盖问题或 P-覆盖问题是研究在服务站的数目和服务半径已知的条件下，如何设立 P 个服务站使得可接受服务的需求量最大的问题。同其它基本问题一样，最大网络覆盖问题也是 NP-困难问(Marks.Daskin)。最初的最大覆盖问题是由 Church RL 和 ReVelle C提出的，他们将服务站最优选址点限制在网络节点上；Church RL和 Meadows ME在确定的关键候选节点集合中给出了一般情况下的最优算法，他们通过线性规划的方法求解，如果最优解不是整数就用分枝定界法求解；Church 和Meadows提出了最大覆盖问题的伪 Hakimi 特性，即在任何一个网络中，存在一个有限节点的扩展集，在这个集合中至少包含一个最大覆盖问题的最优解。Benedict，Hogan 和 ReVelle，Daskin考虑服务系统拥挤情况下的最大覆盖问题，他们把任意一个服务站繁忙的概率当作外生变量，目标函数是服务站可以覆盖的期望需求量最大。Haln Aytug 和 Cem Saydam用遗传算法来求解大规模最大期望覆盖问题，并进行了比较。Fernando Y等对最大期望覆盖问题中排队与非排队的情况进行了对比。Berman研究了最大覆盖问题和部分覆盖问题之间的关系。Oded Berman 和 DmitryKrass 、Oded Berman, Dmitry Krass 和 Zvi Drezner讨论比传统最大覆盖问题更一般的最大覆盖问题，并给出了拉格朗日松弛算法。Orhan Karasakal 和 Esra K.Karasakal讨论了部分覆盖问题，对覆盖程度进行了定义。Jorge H. Jaramillo、Joy Bhary 和 Rajan Batta在选址问题的遗传算法应用研究时介绍了最大覆盖问题遗传算法的操作策略。

9. 怎么求最小面积的三角形覆盖平面上的点集的算法

#include <stdio.h>
#include <math.h>
// 输入最多的点数目
#define MAX_POINTS_AMOUNT 100

struct Point
{
double x,y;
};
// 求点 p1, p2 的距离
double distance(struct Point p1, struct Point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
// 求 a, b, c 中的最大值
double max(double a, double b, double c)
{
return a>=b && a>=c
? a
: b>=a && b>=c
? b
: c;
}

// 判断长度为 a, b, c 的 3条线段能否组成三角形
// 判断依据为：至少有一条边的长度，大于另两条边的长度差（绝对值），小于另两条边的长度和
int canMakeTriangle(double a, double b, double c)
{
return a>fabs(b-c) && a<(b+c) ||
b>fabs(a-c) && b<(a+c) ||
c>fabs(a-b) && c<(a+b);
}

// 判断长度为 a, b, c 的 3条线段能否组成锐角三角形
// 判断依据：根据余弦定理，求出 3 个角的余弦值
int canMakeAcuteTriangle(double a, double b, double c)
{
unsigned int i;
double cos_a, cos_b ,cos_c;
if(canMakeTriangle(a, b, c))
{
cos_a = (b*b + c*c - a*a)/(2*b*c);
cos_b = (a*a + c*c - b*b)/(2*a*c);
cos_c = (a*a + b*b - c*c)/(2*a*b);
return cos_a>0 && cos_b>0 && cos_c>0;
}
return 0;
}

/* 求覆盖 n 个点 points 的最小圆的半径
算法：
只要分别求出所有3点组合覆盖的最小圆，取其中半径最大者即为所求。
确定覆盖3点的最小圆的步骤可以如下：
(1) 若3点组成直角或钝角三角形，或3点共线，此时，最小圆的半径为三边中最长边的一半。
(2) 否则，3点组成锐角三角形，最小圆为3点的外接圆。
(3) 外接圆半径计算方法：
(a) 若3点构成一个三角形(即3点不共线)，
并设3点的坐标为 (x1,y1)，(x2,y2)，(x3,y3)，求出两点(x1,y1)和(x2,y2)之间的距离
L1=sqrt((x1-x2)^2+(y1-y2)^2), 同样求出(x1,y1)和(x3,y3)之间的距离L2，
以及(x2,y2)和(x3,y3)之间的距离L3。
(b) 求出三角形半周长L=(L1+L2+L3)/2以及面积S=sqrt(L*(L-L1)*(L-L2)*(L-L3))。
(c) 根据公式4SR=L1*L2*L3，求外接圆半径R=L1*L2*L3/(4*S)。
参数：
n ： 点数目
points ： n 个点的坐标
start ： 递归参数。表示当前从在 n 个点的第 start 个开始选取。初始值为 0。
selectPointsAmount ： 递归参数。表示当前已经选好了的点数。最多为 3 个。初始值为 0。
selectPoints : 递归参数。表示当前已经选好了的点的坐标数组。初始值为 NULL。
返回：
覆盖 n 个点 points 的最小圆的半径。

*/
double minCircleRadius(unsigned int n, struct Point points[],
unsigned int start, unsigned int selectPointsAmount, struct Point selectPoints[])
{
if(n <= 1)
return 0.0;
if(n == 2)
return distance(points[0], points[1])/2.0;
else
{
if(selectPointsAmount == 3)
{// 已经选好了 3 个点，求能覆盖它们的最小圆的半径

double L1 = distance(selectPoints[0], selectPoints[1]);
double L2 = distance(selectPoints[0], selectPoints[2]);
double L3 = distance(selectPoints[1], selectPoints[2]);
double L = (L1 + L2 + L3)/2.0;
double S = sqrt(L*(L-L1)*(L-L2)*(L-L3));
if(canMakeAcuteTriangle(L1, L2, L3))
{// 能组成锐角三角形
return L1*L2*L3/(4.0*S);
}
else
{// 其他情况：三点共线，组成直角三角形，或锐角三角形
return max(L1, L2,L3)/2.0;
}
}
else
{// 任选 3 个点
double r, minR = 0.0;
unsigned int i;

struct Point temp[3];
if(selectPoints == NULL)
selectPoints = temp;

for(i=start;(n-i)>=(3-selectPointsAmount);i++)
{
selectPoints[selectPointsAmount] = points[i];
r = minCircleRadius(n, points, i+1, selectPointsAmount+1, selectPoints);
if(minR < r)
minR = r;
}
return minR;
}
}
}
int main(int argc, char *argv[])
{
struct Point points[MAX_POINTS_AMOUNT];
unsigned int i,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0; i<n; i++)
scanf("%lf,%lf",&points[i].x, &points[i].y);
printf("%.4lf\n",minCircleRadius(n, points, 0, 0, NULL));
}
return 0;
}
/*
4
4.2,5.6
78.3,3.8
35.4,15.9
29.88,42.56
*/

10. 求8x8棋盘完美覆盖的算法

如果用1*2覆盖的话
任意一块骨牌在棋盘上的摆放都可以用一串长度为64的0、1序列来表示，比如
……0——>表示在棋盘最左上角的位置横着摆上一块骨牌。
考虑到骨牌既可以横着摆也可以竖着摆，一块骨牌在棋盘上的摆放共有2*7*8=112种情况.
这样就可以得到一个112*60大小的矩阵，不妨将该矩阵记为A。矩阵中的元素由0和1组成，矩阵中的每一行都有且只有两个1。
于是上述问题，就转换成怎样从矩阵中找出32行，抽取出来的这32行构成的新的32*60的矩阵，如果能满足每列中有且只有一个1，那么它就是一个完美覆盖。

矩阵的算法如下：
如果矩阵A为空且已经选出了32行，则找到一个完美覆盖，成功返回；
否则选取一个列c，如果c列中不存在1的话，不成功返回;
选择C列中每一个满足A[r,c]=1的行r;
将r值作为解决方案的一个步骤记录下来；
对于r行中每一个A[r,j]=1的j值，从矩阵A中将第j列删除;
对于j列中每一个A[i,j]=1的i值，从矩阵A中将第i行删除;
将已经缩小的矩阵重复进行上面的运算。