覆盖算法
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。