《集合覆盖问题的一种随机近似算法研究.doc》由会员分享，可在线阅读，更多相关《集合覆盖问题的一种随机近似算法研究.doc（8页珍藏版）》请在金锄头文库上搜索。
1、武汉科技大学 组合数学 课程论文 第 1 页集合覆盖问题的一种随机近似算法研究摘 要：集合覆盖问题(SCP)是运筹学中最基本的组合问题，本文给出了集合覆盖问题的一种随机近似算法。给定的子集的集合S和S中每个子集的权值，带权的集合覆盖问题是从S中选择费用和最小的子集使得其并集覆盖E。对E中每一个未被覆盖的元素，以某一精心设计的概率分布选择包含该元素的子集，直到E中所有元素均被覆盖，算法结束。关键词：随机算法；近似算法；集合覆盖1.引言自从集合覆盖问题提出以来，相继有很多学者利用不同思想提出了很多不同的算法，这些算法主要分为完整算法和启发式算法。完整算法基本上建立在分支定界基础上。通过比较和分析，
2、Caprara等人认为CPLEX算法是求解SCP最好的完整算法。但如果问题规模比较大时，其时间代价会非常高。而启发式算法则以牺牲解的精度来取得较好的时间复杂度，在可接受的时间内找到一个最优近似解。在实际问题中，最优近似解一般也能够满足现实的要求。与上述确定算法不同，本文从概率的角度给出了集合覆盖问题的一种随机算法。由于算法的随机性，每次运行输出的覆盖都是随机的，本文证明了算法所求覆盖费用的期望值不超过最优覆盖的B倍，其中。算法每次运行输出的覆盖都可能不同，因此，可以多次运行该算法得到一系列覆盖，从中选择费用最小的，该覆盖很可能接近最优解，甚至可能就是最优解。本算法的时间复杂度是线性的，这为算法
3、的多次运行奠定了基础。另外，当B较小的时候，本文算法可以给出比当前结果较优的解。2.算法(1)设为n个元素的集合，S= 为E的子集的集合。所谓E的覆盖是S的一个子集C，C中元素的并集为E。经典的集合覆盖问题欲求E的一个覆盖C，使得C在E的所有覆盖中所含元素个数最少。形式化描述为输入：集合E= ，S= 输出：，使得，且最小。(2)带权的集合覆盖问题则是更一般的情况。仍设 ，对有一个非负权值叫，表示选择所需要的费用，覆盖C的费用为C中元素权值的和,相应地，问题的输出是求最小费用的覆盖。形式化描述为输人：输出：，使得。且最小化.(3)带权集合覆盖问题的随机近似算法(Algorithm WSC_RA)
4、如下。输入：带权重的集合覆盖问题的一个实例(E，S，W)。输出：集合覆盖C。第一步:以任意顺序排列E中的元素；第二步：选择下一个元素；从中随机选择x，使得 第三步：return C。注意到，包含元素多的集合被选中的概率较大，而在每一轮循环中，算法以较大概率选择权重较小的集合。3.算法近似比的分析定理1假设，其中 ，那么算法WSC_RA是一个在期望意义下近似比为B的近似算法。首先固定输入实例(E，S，W)中元素被试探的顺序，并假设是(E，S，W)的一个最优覆盖，通过WSC_RA算法得到的解C是S的一个随机子集。定义1 对于任意s，定义如下一个变量X令表示X的期望值。表明了集合s实际对覆盖C的贡献
5、，并且变量的分布和的值在执行算法WSC_RA之前已经确定，那么算法的输出结果和期望权重可以表达为现在的目标是适当地把算法WSC_RA的分析一般化。考虑在中的集合，本文将证明这些集合是C的主要组成部分。用另外的参数表示这部分元素。定义2 令为算法WSC_RA计算出的集合，同时这些集合在最优解中。因为在算法执行之前就已经确定了，显然有因此 并且因为。，所以有定理2 ，即算法输出解C的期望值至多是期望权重的B倍。证明：首先通过在集合覆盖实例上做的一个游戏来描述定理的证明。假设集合覆盖实例在开始时，每个的初始资本为，这些权重是在算法执行之前确定的，那么S中集合所有的资本的总和正好是算法的输出结果的期望
6、权重。假设存在一个全局策略，在该策略下，每个集合sS可以分配它的全部资本到它所包含的元素上，并且每个元素能够从包含它的集合(即L(e)中接收到相同数量的资本。然后，每个元素e向在中并且包含它的集合(即)归还它所接收的资本。因此，如果L(e)中仅有一个集合，即，那么所接收到的资本是它所分配给e的资本的倍；如果，那么e向中的每一个集合所归还的资本必然少于该集合所分配给e的资本的倍；如果L(e)中所有的集合都在中，那么e向中的每一个集合所归还的资本恰好等于该集合所分配给e的资本。不难看出，经过上述处理后，每个在中的集合的资本至多增加至原来资本的倍，而没有在中的集合破产了(资本为O)。由此可以看出，现
7、在S中的所有资本至多是开始时元素所拥有资本的B倍。因为每个集合s开始时所拥有的资本为，可以用下式表示这个表达式与定理2中的表达式是等价的。现在唯一需要说明的是，上述把资本分配到元素的资本分配策略是存在的，为什么存在这样的分配策略呢?考虑每个集合sS，如果它所包含的元素中有一个把它选择到覆盖C中，那么它才会在覆盖C中。因此，集合s对于覆盖费用的贡献的期望是由把它选择到C中的元素的贡献组成的。集合s中的元素以一定的概率P把它选择到覆盖C中，从而对C的费用作出贡献。更进一步，元素e对于L(e)中的集合的贡献大小为由此可见，每个元素e对于L(e)中的集合的贡献是相同的。前面的论证是利用分配策略以一种比
8、较明显的方式把覆盖C的费用和最优覆盖的费用关联起来。如果一个元素eE被算法WSC_RA考虑到，然而还没有被覆盖时，则称该元素为关键的。关键元素e使得算法从L(e)中随机地选择一个集合添加到C中。如果随机选择了s到C中，则s是因为关键元素e而被随机选择到C中。定义3 对于任意元素eE和任意定义随机变量如下注意到对于每个元素e，有且仅有一个为非o，而且对于任意的集合，至多有一个它所包含的元素可以选择它到覆盖C中。因此有由此可以得到虽然对于s至多有一个为非零，但是它们的期望值都可以是非零的，因为期望是建立在算法WSC_RA对所有可能的选择的基础上。需要说明的是，对于任意，任意5，这个说明隐含了所期望
9、的分配策略的存在性。这是因为每个集合sS分配价值为的资本给它所包含的元素e，因而，每个元素可以从包含它的集合接收到相同价值的资本。因此有以上的分配策略。定理3 对于任意eE，任意s，。证明 4 结束语给定图以及定义在顶点上的费用函数W，所谓顶点覆盖S是顶点集合的一个子集，满足对于每条边，u和v至少有一个被S覆盖。最小费用顶点覆盖问题是要求一个费用最小的顶点覆盖。把边集E看成要覆盖的对象，每个顶点看成它所关联边的集合，这样顶点覆盖问题就转化成集合覆盖问题。每条边包含在2个子集中，即B=2，因此本文算法所求的顶点覆盖费用的期望值不会超过最优顶点覆盖的2倍。参考文献1 金银秋 ；最小覆盖算法及正确性证明；计算机应用与研究； 1993(2),39-4t2 宋恩民；求解析取范式永真性问题的一个近似快速算法；科学通报，1992(8)3 宋恩民，陈亮；求Ramsey数最优下届值的递归算法；华中科技大学报；1992(6)4 郝忠孝，郭景峰；一种基于超图的最小覆盖集求法；计算机研究与发展；1990(10)5 于磊，叶静；支持大规模变量集的最小覆盖迭代搜索算法；计算机辅助计算与图形学学报；2008,6,Vol.20,No.6
