覆蓋演算法
A. 近似演算法的集合覆蓋問題的近似演算法
問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數費用c(u,v)。要找出G的最小費用哈密頓迴路。
集合覆蓋問題的一個實例〈X,F〉由一個有限集X及X的一個子集族F組成。子集族F覆蓋了有限集X。也就是說X中每一元素至少屬於F中的一個子集，即X= 。對於F中的一個子集CF，若C中的X的子集覆蓋了X，即X= ，則稱C覆蓋了X。集合覆蓋問題就是要找出F中覆蓋X的最小子集C*，使得
|C*|=min{|C||CF且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|})。由此即知，該演算法是一個多項式時間演算法。
B. 棋盤覆蓋問題的演算法實現
下面討論棋盤覆蓋問題中數據結構的設計。
（1）棋盤：可以用一個二維數組board[size][size]表示一個棋盤，其中，size=2^k。為了在遞歸處理的過程中使用同一個棋盤，將數組board設為全局變數；
（2）子棋盤：整個棋盤用二維數組board[size][size]表示，其中的子棋盤由棋盤左上角的下標tr、tc和棋盤大小s表示；
（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是該特殊方格在二維數組board中的下標;
（4） L型骨牌：一個2^k×2^k的棋盤中有一個特殊方格，所以，用到L型骨牌的個數為(4^k-1)/3，將所有L型骨牌從1開始連續編號，用一個全局變數t表示。
設全局變數t已初始化為0，分治法求解棋盤覆蓋問題的演算法用C++語言描述如下：
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
int s, t1; //t1表示本次覆蓋所用L型骨牌的編號
if (size == 1) return; //棋盤只有一個方格且是特殊方格
t1 = ++t; // L型骨牌編號
s = size/2; // 劃分棋盤
if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盤中
ChessBoard(tr, tc, dr, dc, s); //遞歸處理子棋盤
else{ //用 t1號L型骨牌覆蓋右下角，再遞歸處理子棋盤
board[tr + s - 1][tc + s - 1] = t1;
ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
}
if (dr < tr + s && dc >= tc + s) //特殊方格在右上角子棋盤中
ChessBoard(tr, tc+s, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋左下角，再遞歸處理子棋盤
board[tr + s - 1][tc + s] = t1;
ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
}
if (dr >= tr + s && dc < tc + s) //特殊方格在左下角子棋盤中
ChessBoard(tr+s, tc, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋右上角，再遞歸處理子棋盤
board[tr + s][tc + s - 1] = t1;
ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
}
if (dr >= tr + s && dc >= tc + s) //特殊方格在右下角子棋盤中
ChessBoard(tr+s, tc+s, dr, dc, s); //遞歸處理子棋盤
else { //用 t1號L型骨牌覆蓋左上角，再遞歸處理子棋盤
board[tr + s][tc + s] = t1;
ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}
C. 請問互聯網覆蓋率怎樣計算
不是的，方法有很多種，比較常用的是地區覆蓋法，就是某個地區有人在使用它的網路，那就表示已經覆蓋～相反就是沒有覆蓋
D. 如何計算覆蓋率
指某一商品在所有潛在的銷售網點的覆蓋比率。例如：可口可樂在全國100萬的潛在銷售網點，其有80萬已進貨銷售，則其市場覆蓋率為80％。 市場覆蓋率是一個與市場佔率相關的一個指標。它是本產品的投放地區占應銷售地區的百分比。市場覆蓋率按照從低密度的覆蓋到高密度的覆蓋可以分為獨家分銷、選擇分銷和密集分銷三種類別。 市場覆蓋率= 本產品投放地區數 /全市場應銷售地區數 X 100%
E. 棋盤覆蓋演算法
import java.util.*;
public class TestChessBoard {
public static void main(String[] args) {
int tr=0,tc=0,dr=1,dc=2,size=8;
ChessBoard.chessBoard(tr,tc,dr,dc,size);
ChessBoard.display();
}
}
class ChessBoard {
public static int tile = 0;
public static int[][] board= new int[10][10];
public static void chessBoard (int tr,int tc,int dr,int dc,int size) {
if(size == 1) return;
int t = tile++ , s = size/2;
if(dr<tr+s && dc<tc+s){
chessBoard(tr,tc,dr,dc,s);
}else {
board[tr+s-1][tc+s-1] = t;
chessBoard(tr,tc,tr+s-1,tc+s-1,s);
}
if(dr<tr+s && dc>=tc+s){
chessBoard(tr,tc+s,dr,dc,s);
}else {
board[tr+s-1][tc+s] = t;
chessBoard(tr,tc+s,tr+s-1,tc+s,s);
}
if(dr>=tr+s && dc<tc+s) {
chessBoard(tr+s,tc,dr,dc,s);
}else {
board[tr+s][tc+s-1] = t;
chessBoard(tr+s,tc,tr+s,tc+s-1,s);
}
if(dr>=tr+s && dc>=tc+s) {
chessBoard(tr+s,tc+s,dr,dc,s);
}else {
board[tr+s][tc+s] = t;
chessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
}
public static void display() {
for(int i=0;i<8;i++){
for(int j=0;j<8;j++) {
System.out.print(" "+board[i][j]);
}
System.out.println();
}
}
}
F. 試給出兩種以上的典型無線感測器網路覆蓋演算法，並詳細分析其演算法原理及其優缺點。
攻擊者可以通過竊聽。遠程監聽還可以使單個攻擊者同時獲取多個節點的傳輸的信息。如何進一步加快其時空數據處理和管理的能力，開發出新的模式將是非常有必要的。
無線通訊的標准問題
G. 線段覆蓋問題 演算法及程序
我的演算法:
我採用貪心的演算法, 按照左端點排序, 建立一個以線段右端點為關鍵字的大根堆.
依次嘗試插入線段, 對於當前的一個線段, 如果能夠覆蓋,顯然我們選擇覆蓋, 而如果不能覆蓋, 我們進行一下討論.
首先我們需要知道
(1) 如果線段發生相交, 那麼只可能是兩條線段相交:
理由: 對於前面的所有線段,貪心法保證,也顯然,已經滿足兩兩不相交了, 那麼如果當前的線段,和另外兩條線段相交, 則必然將一條線段包含, 而我們按照線段左端點排序, 按次序嘗試覆蓋, 因此這種情況是不存在的.
那麼我們假設當前的線段是 [L0, R0] 發生相交的線段是 [L1, R1]
即有 L0 >= L1 R0 <= R1 這兩條線段是不能共存的.
顯然,我們要從中留下一個而捨去一個, 捨去哪個呢? 就應該選擇右端點小的那個! 為什麼? 因為右端點越靠左,對後面的線段的覆蓋產生的影響(就是發生覆蓋的機會)就越小! 很直觀的, 我們可以知道這種貪心法的正確性.
問題就解決了
時間復雜度 O(N log N)
我寫的代碼:
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 10010;
struct event {
int l, r;
}e[maxn];
struct __Comp {
inline int operator() (const event &a, const event &b) const {
return a.r < b.r;
}
};
priority_queue<event, vector<event>, __Comp> hp;
int n, l, r;
inline
int comp(const event &a, const event &b) {return a.l < b.l;}
int main() {
scanf("%d", &n);
for (int i=0;i<n;++i) {
scanf("%d %d", &l, &r); e[i] = (event){l<?r, l>?r};
}sort(e, e+n, comp);
for (int i=0;i<n;++i) {
if (!i) {hp.push(e[0]); continue;}
if (e[i].l >= hp.top().r) hp.push(e[i]);
else
if (hp.top().r > e[i].r) {
hp.pop(); hp.push(e[i]);
}
} printf("%d\n", hp.size());
scanf("%*s");
}
H. 求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行刪除;
將已經縮小的矩陣重復進行上面的運算。
I. 近似演算法的頂點覆蓋問題的近似演算法
問題描述：無向圖G=(V,E)的頂點覆蓋是它的頂點集V的一個子集V』，使得若(u,v)是G的一條邊，則v∈V』或u∈V』。頂點覆蓋V』的大小是它所包含的頂點個數|V』|。
VertexSet approxVertexCover ( Graph g )
{ cset=NULL；
e1=g.e；
while (e1 !=NULL) {
從e1中任取一條邊(u,v)；
cset=cset∪{u,v}；
從e1中刪去與u和v相關聯的所有邊；
}
return c
}
Cset用來存儲頂點覆蓋中的各頂點。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點加入cset中，並將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。
圖(a)～(e)說明了演算法的運行過程及結果。(e)表示演算法產生的近似最優頂點覆蓋cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。