最小集合覆盖
- 格式：doc
- 大小：287.50 KB
- 文档页数：9
最小集合覆盖问题（MSCP）
（1）含义：给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。 最小集合覆盖问题的一个实例〈X,F〉由一个有限集X及X的一个子集族F组成。子集族F覆盖了有限集X。也就是说X中每一元素至少属于F中的一个子集，即X=F 。对于F中的一个子集C，若C中的X的子集覆盖了X，即X= C，则称C覆盖了X。集合覆盖问题就是要找出F中覆盖X的最小子集C*，使得
且C覆盖X}
（2）含义：S是一个集合，S1,S2,...,Sn是S的子集，且构成S的覆盖，即1niiSS，求最小覆盖问题。
（3）含义：最小集合覆盖问题是运筹学研究中的一个基本的组合优化问题，它通常描述成如下的一个覆盖问题：从一个m行、n列的0-1矩阵（aij）mxn中选出若干列盖住所有的行，使得付出的代价最小。
（4）缺点：1、具有很高的计算复杂度；
2、容易受局部最优解的影响；
（5）应用领域：集合覆盖问题在现实生活和生产中有许多重要应用,如生产、投资决策以及项目选择，分子生物学，调度问题，信息检索、错误诊断和恢复。集装线平衡，油轮行程安排及开关理论，电路设计，运输车辆路线安排。.
（6）求解方法：
1、 运用DNA粘贴模型求解步骤：
考虑简单无向图G=（V，E）的最小顶点覆盖问题，令顶点集V（G）={v1,v2,…,vn}，边集E(G)={e1,e2,…, me}。最小顶点覆盖问题的DNA算法为：
步骤1 对图G的每个顶点进行ＤＮＡ编码，生成图Ｇ的所有顶点的闭环ＤＮＡ。
步骤２ 以每条边为约束通过删除实验，在闭环DNA上删除掉与边相关联的一个顶点。m次删除实验后，产生所有覆盖的补集。
步骤3 通过电泳实验，选择最长的闭环DNA，产生最小覆盖的补集。
步骤4 检测实验结果，得到最小覆盖。
2、 人工神经网络求解步骤：
1. 设置t=0,,,,;ABC
2. 读入图G的相邻矩阵（ija）(i,j=1,2,…,p)文件；
3. 计算神经元之间的权重tjw和输入偏置tI
111;(());tjtjtjpptttjtjWCaIABvdCa
4. 在0的附近随机的产生()(1,2,...,)iutip的初始值； 5. 计算()(1,2,...,)iutip的值；
()1(1tanh)2itutv；
6. 利用神经元动态方程来计算()(1,2,...,)iutip；
1()()pitjjtjutWvtI
7. 根据一阶Euler法计算(1):(1)()()iiiiututututt；这里i=1,2,…,p,
t取1.
如果系统达到平衡状态，终止程序，否则返回5.
其中A,B,C以及表示实验参数
3、 遗传模拟退火算法求解步骤；以组播组个数S=100为例
步骤1.采用二进制编码，随机产生100个解构成初始种群，每个个体对应一个genetree。
步骤2.采用二元锦标赛选择从种群中选出两个个体p1和p2。
步骤3.采用熔合操作组合p1和p2，生成新解C。
步骤4.将C中的一个“1”变为“0”，并删除对应的树。
步骤5.采用自适应操作保证所有组都被覆盖。
步骤6.如果C与种群中的解相同，返回步骤2.
步骤7.用C代替种群中适应函数值最大的解。
步骤8.循环执行40次。从种群中选出适应函数值最小的解。
4、 贪心法求解步骤；
(1) 从某一格局出发，选择平均代价最小的列来覆盖那些还没有被覆盖的行，若有多列，那么
(2) 选择代价最小的列，若还有多列，那么
(3) 选则序号最小的列。
按此策略选择一列后，便得到新的格局。从此新格局出发，再次是用贪心法选择策略，知道所有行都被覆盖或剩下的列中已没有列可覆盖照顾那些未被覆盖的行。对用贪心法选择策略得到的解，需将冗余的列从解中剔除，以提高解的优度。即：对解中某列就，它盖住p行i1，i2，…ip,若可用解中除列j外的若干列盖住p行i1，i2,…ip,则可将列j从解中剔除。这时剩下的列仍能盖住所有的行，而代价却减小了。
例子
假设v1, v2, „ , v7是7个哨所,监视着11条路段(如下图所示),为节省人力,问至少
需要在几个哨所派人站岗,就可以监视全部路段? 即求最小顶点覆盖问题.
{v1, v3, v5, v6}和{v1, v3, v5, v7}都是最小点覆盖, 所以至少需要在4个哨所派人站
岗来监视全部路段.
顶点覆盖问题的近似算法
VertexSet approxVertexCover ( Graph g )
v2 v1
v3 v7
v6 v5 v4 {
cset=
e1=g.e；
while (e1 != ) {
从e1中任取一条边(u,v)；
cset=cset∪{u,v}；
从e1中删去与u和v相关联的所有边；
}
return c
}
2、
2、
(5)程序：MALTAB实现了这样一个图形，怎样用MALTAB语句构建一个最小圆，能覆盖上面所有的九个点。
这个图的语句：
x=[22 8 4 51 38 17 81 18 62]
y=[38 13 81 32 11 12 63 45 12]
plot(x,y,'*')%
grid on%
% 算法思路：
% 1. 在点集中任取3点A,B,C。
% 2. 作一个包含A,B,C三点的最小圆,圆周可能通过这3点，也可能只通过其中两点,但包含第3点.后一种情况圆周上的两点一定是位于圆的一条直径的两端。
% 3. 在点集中找出距离第2步所建圆圆心最远的D点，若D点已在圆内或圆周上，则该圆即为所求的圆，算法结束.否则执行第4步。
% 4. 在A,B,C,D中选3个点,使由它们生成的一个包含这4个点的圆为最小，这3 点成为新的A,B,C，返回执行第2步。
% 若在第4步生成的圆的圆周只通过A,B,C,D 中的两点，则圆周上的两点取成新的A和B,从另两点中任取一点作为新的C。
clear all;close all;clc;
x=[22 8 4 51 38 17 81 18 62]
y=[38 13 81 32 11 12 63 45 12]
plot(x,y,'*');hold on;
grid on%
set_3P=nchoosek(1:length(x),3);
AI=set_3P(1,1);
BI=set_3P(1,2);
CI=set_3P(1,3);
A=[x(AI) y(AI)];
B=[x(BI) y(BI)];
C=[x(CI) y(CI)];
while 1
R=minCirclePoints3(A,B,C);
cr=[R(1),R(2)];
r=zeros(1,length(x));
for i=1:length(x)
r(i)=sqrt((x(i)-cr(1))^2+(y(i)-cr(2))^2);
end;
maxValue=max(r); %或者N=max(r(:))
[mc]=find(maxValue==r);
if r(mc)<=R(3)%没有点在圆外，结束回家吃饭去
alpha=0:pi/20:2*pi;%角度[0,2*pi]
plot(cr(1)+R(3)*cos(alpha),cr(2)+R(3)*sin(alpha),'--r');%中心点在（R(1),R(2)）半径为R(3)的圆
axis equal;
break;%所有点都被圆覆盖
else
%距离圆心最远的点在圆外
end;
D=[x(mc),y(mc)];
P=[A;B;C;D];%保存这四个点的坐标
DI=mc; set_3P=nchoosek([AI,BI,CI,DI],3);
rSet=[];
for i=1:length(set_3P)
A=[x(set_3P(i,1)) y(set_3P(i,1))];
B=[x(set_3P(i,2)) y(set_3P(i,2))];
C=[x(set_3P(i,3)) y(set_3P(i,3))];
R=minCirclePoints3(A,B,C);
rSet=[rSet;[R,i]];%每行：圆心坐标,半径,第几组(每组包括随机的三个点)
end;
rSet=sortrows(rSet,3);%按照半径排序
% 在四个圆中找一个最小半径圆包含这四个点
for i=1:size(rSet,1)
for j=1:4
if sqrt((rSet(i,1)-(P(j,1) ))^2+ ( rSet(i,2)-(P(j,2)))^2) >rSet(i,3)%这个圆不行
break;
end
end;
if j>4%第i组三个点产生的圆可行--必然可以找到一个
break;
end;
end;
mc=rSet(i,4);
A=[x(set_3P(mc,1)) y(set_3P(mc,1))];
B=[x(set_3P(mc,2)) y(set_3P(mc,2))];
C=[x(set_3P(mc,3)) y(set_3P(mc,3))];
end;
%总结：根据算法我写的这个程序有个隐藏的问题，由于要看比赛了，没时间再纠正这个问题了。
-------------------------------------------------------------------------------
function R=minCirclePoints3(A,B,C)
X=[A(1) B(1) C(1)];
Y=[A(2) B(2) C(2)];
%计算三边的长度AB BC CA
len=[sqrt((X(1)-X(2))^2+(Y(1)-Y(2))^2) sqrt((X(2)-X(3))^2+(Y(2)-Y(3))^2)
sqrt((X(3)-X(1))^2+(Y(3)-Y(1))^2)];
%在非特殊情况下计算三角形三角的余弦值 cosA,cosB,cosC
if(sum(len>0)==3)
abc=[cosABC(len(2),len(1),len(3)) cosABC(len(3),len(1),len(2))
cosABC(len(1),len(2),len(3))];
