最大覆蓋演算法

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行刪除;
將已經縮小的矩陣重復進行上面的運算。