集合覆盖近似算法

近似算法最小顶点覆盖
最小顶点覆盖问题是指在一个图中找到最小的顶点集合，使得每一条边都至少有一个端点在这个集合中。

最小顶点覆盖的算法很多，其中一种近似算法是贪心算法。

贪心算法的基本思路是，每次选择当前能选择的最优解来扩大覆盖集合。

对于最小顶点覆盖问题，我们可以选择一些顶点来组成覆盖集合，使得每条边都至少有一个端点在集合中。

一个比较直观的近似算法是：
1. 初始化覆盖集合为空。

2. 对于每条边，如果其中一个端点不在覆盖集合中，则将这个端点加入覆盖集合。

3. 重复步骤2，直到所有边都被覆盖。

这个算法的复杂度是O(E)，其中E是边数。

虽然它不保证得到精确解，但是在实际中效果还是很不错的。

事实上，该算法的近似比例是2，也就是说，它得到的解最多是精确解的两倍。

集合覆盖问题 NP问题的近似解Set Cover problem是计算机算法复杂度领域的经典问题。

问题如下定义：⾸先有⼀个元素集合U，给定⼀系列集合，各集合之中含可能有⼀些共同的元素（如图所⽰）。

要求访问最少的集合，可以得到U中所有的元素，求出满⾜要求的最少数量的集合，它是Karp’s 21个NP-complete问题之⼀。

可以给出公式定义：给定⼀个元素集合{U}和集合{S}，Si中的元素属于U，即S是U的⼦集集合。

我们要求的⼀个覆盖就是⼀个集合C其元素集合之并等于U即：。

⽤图⽰表明：Input：Output：Set cover问题通常在我们寻求⾼效获取被package起来的项或者寻求⼀种最优的项表述时出现，显然找到⼀个cover很简单，但我们⽬的是求的最优，这样才能更好的节约成本。

我们知道，所有的NP-C（NP完全问题）都还没有多项式时间算法。

⽽当我们遇到这类问题时我们通常采⽤只对特殊问题求解，动态规划或分⽀定界，概率算法，只求近似解或者启发式⽅法求解。

下⾯就使⽤贪婪算法给出近似解：⾸先给出如下函数定义给出贪婪算法：下⾯对此算法进⾏分析：此贪婪算法已被证明是set cover问题的⼀个多项式时间复杂度，（1+In r）ratio近似算法，其中r是输⼊S中集合的最⼤的集的势。

证明：假设S1，S2…Sj是通过贪婪算法依次选择的集合，Ci={S1，S2…Si}，opt是满⾜集合覆盖最优解的集合数，由于贪婪规则，显然，当我们选择Si+1时Si+1必定覆盖了当前还未被Ci覆盖的最多元素。

还未被Ci覆盖的元素是|U|-f(Ci)，他们可以被opt个⼦集合最优覆盖。

因此，按平均来算，最优解集合的⼀个⼦集可以覆盖（|U|-f(Ci)）/opt个没有被Ci覆盖的元素，因此推出：解决Set cover问题的贪婪算法已经被证明是解决set cover问题的最可能的多项式时间复杂度近似算法。

第9章近似算法第9章近似算法1第9章近似算法迄今为止，所有的NP完全问题都还没有多项式时间算法。

对于这类问题，通常可采取以下几种解题策略。

(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解本章主要讨论解NP完全问题的近似算法。

239.1 近似算法的性能若一个最优化问题的最优值为c*，求解该问题的一个近似算法求得的近似最优解相应的目标函数值为c，则将该近似算法的性能比定义为η= 。

在通常情况下，该性能比是问题输入规模n的一个函数ρ(n)，即≤ρ(n)。

?c c c c *,*max ?c c c c *,*max 该近似算法的相对误差定义为λ= 。

若对问题的输入规模n，有一函数ε(n)使得≤ε(n)，则称ε(n)为该近似算法的相对误差界。

近似算法的性能比ρ(n)与相对误差界ε(n)之间显然有如下关系：ε(n)≤ρ(n)-1。

**c c c ?**c c c ?9.2 顶点覆盖问题的近似算法问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V 的一个子集V’?V，使得若(u,v)是G的一条边，则v∈V’或u∈V’。

顶点覆盖V’的大小是它所包含的顶点个数|V’|。

VertexSet approxVertexCover( Graph g ){ cset=?；e1=g.e；while (e1 != ?) {从e1中任取一条边(u,v)；cset=cset∪{u,v}；从e1中删去与u和v相关联的所有边；}return c}Cset用来存储顶点覆盖中的各顶点。

初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset 中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边。

即e1为空。

49.2 顶点覆盖问题的近似算法图(a)～(e)说明了算法的运行过程及结果。

(e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成。

求解集合覆盖问题的离散动态凸化方法刘秀梅;欧阳菲【摘要】集合覆盖问题是一个基本的组合优化问题,它是NP(多项式复杂程度的非确定性)完全问题.通过罚函数把问题转化为一个无约束最优化问题,给出一个辅助函数.它和问题有相同的离散全局极小解,设计一个算法,通过极小化该辅助函数得到问题的一个近似离散全局极小解.数值试验表明,算法对求解集合覆盖问题是有效的.【期刊名称】《宁德师范学院学报（自然科学版）》【年(卷),期】2019(031)002【总页数】5页(P120-123,133)【关键词】集合覆盖;离散全局极小解;罚函数;辅助函数【作者】刘秀梅;欧阳菲【作者单位】泉州理工学院通识教育中心,福建泉州362000;泉州理工学院通识教育中心,福建泉州362000【正文语种】中文【中图分类】O224集合覆盖问题是一个经典的NP(多项式复杂程度的非确定性)难问题,相继有很多学者利用不同思想提出了很多优化算法.Balas 和Ho 提出了割平面法[1],Fisher 和Kedia 提出了对偶启发式算法[2];Beasley 和Jornslen 结合拉格朗日启发式算法,用约束条件排除可行解的方法，Gomory f-cuts 和改进的分支策略解决了集合覆盖问题[3];Jacobs 和Brusco 开发了模拟退火算法[4];Beasley,Chu 以及Corne 等提出了用遗传算法解决集合覆盖问题[5].这些算法主要分为精确算法和启发式算法.如果问题规模比较大时,精确算法时间代价非常高,启发式算法则以牺牲解的精度来取得较好的时间复杂度.本文用罚函数的方法，把问题转化为一个无约束最优化问题,给出一个辅助函数,它和问题有相同的离散全局极小解.设计一个算法,通过极小化该辅助函数得到问题的一个近似离散全局极小解.1 集合覆盖问题介绍集合覆盖问题通常描述为:从一个m 行,n 列的0-1 矩阵（aij）m×n中选出若干列盖住所有的行,使得盖住所有行所付出的代价最小.它可用问题（A）二值整数规划来表示：式中:cj表示第j 列的代价;xj取0 或1,取1 表示第j 列包含在解中,取0 表示第j 列没有包含在解中;aij=1表示第j 列盖住了第i 行,aij=0 表示第j 列没有盖住第i 行.2 罚函数一般地,一个合适的罚函数对不可行点产生正的惩罚,对可行点不产生惩罚.问题（A）的罚项函数的定义如下：其中，，…，m}，当xj为问题（A）的可行解时,p（x）=0.对所有x∈I，p（x）≥0.精确罚问题的定义为:其中，μ＞0 为惩罚参数,称为罚因子.设，则f（x）=g（x）+μp（x）.定理1 如果x*是问题（A）的最优解,且μ=g（x*）,则x*是问题（P）的最优解.证明因为x*是问题（A）的最优解,所以也是问题（P）的可行解,故p（x*）=0，则f（x*）=g（x*）+μp（x*）=g（x*）.对所有x∈I,有f（x）=g（x）+μp（x）=g（x）+g（x*）p（x）.当p（x）≠0 时，，而aij，xj为0 或1，故，所以p（x）=1，f（x）=g（x）+g（x*）p（x）=g（x）+g（x*）＞g（x*）.当p（x）=0 时，x∈F，g（x）＞g（x*），此时f（x）=g（x）＞g（x*）.综上可知,对所有x∈I，f（x）＞f（x*），即x*是问题（P）的最优解.定理2 如果xμ*是问题（P）的最优解和问题（A）的可行解,则xμ*是问题（A）的最优解.证明根据定理2 的假设，有f（xμ*）=g（xμ*）+μp（xμ*）=g（xμ*）＜f （x），∀x∈I，即g（xμ*）＜g（x）+μp（x）.则对∀x∈F,有g（xμ*）＜g （x），即xμ*是问题（A）的最优解.3 邻域的概念在组合优化中,欧氏距离的概念通常不再适用.因此,需要重新定义邻域的概念.定义1 对∀x∈I，若集合N（x）={x，φi（x），i=1，…，n}，则称N（x）为x 的邻域,其中φi（x）表示x 的第i 个分量为,其余分量不变.定义了邻域之后,类似连续函数,可以定义局部最优和全局最优.定义2 设x0∈I.若对∀x∈N（x0）,有f（x）≥f（x0）,则称x0为问题（P）的离散局部极小解；若对∀x∈I,有f（x）≥f（x0）,则称x0为问题（P）的离散全局极小解.从上述定义可知,问题（P）的离散全局极小解也一定是问题（P）的离散局部极小解.本文通过邻域搜索算法求问题（P）的离散局部极小解,算法1 的具体步骤如下：1)取点x0∈I.2)若x0为问题（P）的离散局部极小解,停止;否则，取x∈N（x0）,使f（x）＜f （x0）.3)令x0:=x,转步骤2).4 辅助函数及其性质上述邻域搜索算法找到的一般只是问题（P）的离散局部极小解,本文给出一个不同于文献[6]的辅助函数.此辅助函数和问题（P）有相同的离散全局极小解,设计一个算法,从一个初始点出发,极小化该辅助函数,来找问题（P）的比当前离散局部极小解更好的解.4.1 辅助函数假设x1*为问题（P）当前最好的离散局部极小解,且x0是问题（P）的离散局部极小解,使得f（x0）≥f（x1*）.构造如下辅助函数：其中,k 为非负参数.在此范数“‖·‖”表示1-范数,即，构造以下辅助问题：4.2 辅助函数T（x，k）的性质类似于文献[6]中相关定理之证明,可以得出辅助函数T（x，k）相关的一些性质.定理3 若x0是问题（P）的离散局部极小解,且f（x0）≥f（x1*）,则x0是问题（AP）的离散局部极小解.定理4 s1={x∈I:f（x）＜f（x1*）}，s2={x∈I:f（x）≥f（x1*）},对所有x∈s1，y∈s2，T（x，k）＜T（y，k）成立.由定理4 可得：推论1 若x1*不是问题（P）的离散全局极小解,则s1={x∈I:f（x）＜f（x1*）}≠Ø，且问题（AP）的所有离散全局极小解在集合s1中.定理5 假设x1*不是问题（P）的离散全局极小解，y∈s1={x∈I:f（x）＜f（x1*）}.若y 是问题（AP）的离散局部极小解,则y 是问题（P）的离散局部极小解,反之成立.由推论1 和定理5 可得以下结论：推论2 若x1*不是问题（P）的离散全局极小解,则问题（P）和问题（AP）有相同的离散局部极小解和离散全局极小解.定理6对∀x=（x1，x2，…，xn）T∈I,若x≠x1*=（x11*，x12*，…，x1n*）T,且x1*∈I,那么存在y=（y1，y2，…，yn）T∈N（x），使得‖y-x1*‖＜‖x-x1*‖.证明若x≠x1*,则存在j∈{1，2，…，n},使xj≠x1j*.令yi=xi，i=1，2，…，n（i≠j）,则显然,y∈N（x）.定理7 对于函数T（x，k）,有以下结论：1）对∀x∈s2={x∈I:f（x）≥f（x1*）},若存在y∈N（x）,使得f（y）＜f（x1*）,则x 不是问题（AP）的离散局部极小解.2）对∀x∈s2，x≠x1*，令若k＞L（x）,则x 不是问题（AP）的离散局部极小解.3）若,则对所有x∈s2，x≠x1*，x 不是问题（AP）的离散局部极小解.定理7 的结论2）和3）说明,当极小化函数T（x，k）时,若离散局部极小解一直在集合s2中,那么通过增加k 值,T（x，k）的极小解可以从离散局部极小解中跳出. 定理8 设z∈N（x），且f（x）＞f（z）≥f（x1*）,则T（z，k）＜T（x，k）.当且仅当下列条件之一成立：1）k=0;2）k＞0 且‖z-x0‖≤‖x-x0‖;定理8 说明,若k 太大,那么在一些情况下T（x，k）的下降点不会在集合s2中.所以为了得到比x1*更小的离散局部极小解,当从一个初始点极小化T（x，k）时,k 值不能太大.但是定理7 又表明：要绕过当前的离散吸引区域时,k 必须足够大,这与定理8 矛盾了.因此,在减小T（x，k）时,应先取k=0,然后再慢慢增加k 值.5 动态凸化方法下面给出通过解问题（AP）来得到问题（P）的离散全局极小解的算法2.算法2 的步骤如下[6]：1）随机选一点x∈In，用算法1 减小f（x）,得到问题（P）的一个离散局部极小解x1*.令N1为一个充分大的数,δk为一个正数.令Ν＝0.2）选择一点x0∈In,使x0是问题（P）的一个离散局部极小解，且f（x）≥f（x1*），用k，x0，x1*构造函数T（x，k）.3）令k=0，N=N+1.若N＞Nl，则转到步骤6）;否则随机找一点y∈In,转到步骤4）.4）用算法1 从y 开始极小化T（x，k）.假设x′是得到的一个离散局部极小解.若x′≠x0且f（x′）＞f（x1*），则令k=k+δk，y=x′，重复步骤4);若x′=x0，则转到步骤3）;若f（x′）＜f（x1*）,则转到步骤5).5）令x1*=x′,转到步骤2）.6）停止.输出x1*和f（x1*）,作为问题（P）的近似全局极小解和极小值.在此算法中,最初,令k=0,随机选一点x∈In,用算法1 从y 开始极小化T（x，k）.若极小化的序列收敛于x′≠x0且f（x′）＞f（x1*）,则增加k 值,减少T（x，k）从x′开始.若此时极小化的序列收敛于x″≠x0且f（x″）＞f（x1*）,则由定理7,k 值太小了,增加k 值,极小化T（x，k）从x″开始,直到极小化的序列收敛于x0或{x∈I:f （x）＜f（x1*）}中的一个点.若极小化的序列收敛于x0，重复以上过程.若极小化的序列收敛{x∈I:f（x）＜f （x1*）}中的一个点,那么由定理7,已经找到问题（P）的比x1*小的离散局部极小点,留下x1*,重复以上过程.6 实验结果与分析对提出的算法,本文编写了程序,用OR-Library 中的第一个例子进行测试,这个实例中,列的代价cj是从1 到100 的整数中随机选出的,其中每行至少被两列覆盖.对实例运行15 次,得到的离散局部极小值为157.此实例用贪心算法求得的离散局部极小值为186.本文算法得到的结果比贪心算法得到的结果好,但是速度比贪心算法要慢.与其他算法相比,本文算法操作简便,容易理解.7 结论集合覆盖问题在实际生活中的应用非常广泛,因此,研究它的求解方法是非常有意义的.集合覆盖问题是一个约束最优化问题,本文用罚函数的方法,把约束吸收到目标函数中,通过求解该罚函数的无约束优化问题的最优解来得到原约束优化问题的最优解.构造了一个新的辅助函数,并证明了该辅助函数和集合覆盖问题有相同的离散全局极小解.本文用离散动态凸化方法来求解集合覆盖问题,该算法是一个近似算法,算法从一个随机初始点出发开始极小化辅助函数,使极小化序列逐渐逼近问题的最优解.参考文献：【相关文献】[1]EBALAS E,HO A.Set covering algorithms using cutting planes,heuristics and subgradient optimization：a computational study[J].Mathematical Programming,1980,12：37-60. [2]FISHER M.Optimal solution of set covering partitioning problems using dual heuristics[J].Management Science,1990,36：674-683.[3]BEASLEY J E,JORNSTEN K.Enhancing an algorithm for set coveringproblems[J].European Journal of Operational Research,1992,58:293-300.[4]JACOBSL，BRUSCOM.Alocal-search heuristic forlarge set covering problems[J].Naval Research Logistics,1995,42：1129-1140.[5]BEASLEY J E,CHU P C.A genetic algorithm for the set covering problem[J].European Journal of Operational Research,1996,94：392-400.[6]ZHU W X,FAN H.A discrete dynamic convexized method for nonlinear integer programming[J].Journal of Computational and Applied Mathematics,2009,223（1）：356-373.。

一种求解最小集合覆盖问题近似解的组合优化方法专利名称：一种求解最小集合覆盖问题近似解的组合优化方法技术领域：本发明涉及一种求解最小集合覆盖问题近似解的组合优化方法，属于组合优化问题的求解技术领域。

背景技术：最小集合覆盖问题是一种抽象的组合优化问题。

该问题给出一系列元素和一系列集合，其中每个集合包含一个或者多个元素，并且每一个集合拥有一个权值。

最小集合覆盖问题即是要从这些集合中挑选一组集合，使得每一个元素至少出现在这一组集合中的某个集合中(即形成一个对所有元素的覆盖)，并且要使得这一组集合的权值之和最小。

形式化地描述，有n个元素U= {1，2，. . .，n}，和m个集合C = (S1, S2,, Sj，其中对于任意1=1，2，...，!11有友￡队并且￥技)为集合SJA权值。

最小集合覆盖问题要寻找C的一个子集C*使得Esec*切⑷:最小，同时满足Usee* = 最小集合覆盖问题广泛存在于工业生产中，例如物流仓储的布局、基站的布局、故障诊断、分布式系统、无线传感器网络配置、调度等等。

然而由于最小集合覆盖问题为NP难问题，在极有可能成立的NP幸P的假设条件下，不存在解决该问题的高效的算法(即多项式时间内能够求解最优解的算法)。

目前工业应用上，用于处理类似NP难问题的方法主要为启发式搜索算法，包括模拟退火算法、演化算法、粒子群算法等，以期望取得较好的解。

然而这些算法对于取得的解过于随意，解的质量并没有任何保障，有可能获得很差的解从而导致应用中过大的成本开销等问题。

发明内容发明目的本发明主要针目前求解最小集合覆盖问题的启发式算法，缺乏对取得的解的质量的保障这一问题，提出一种求解最小集合覆盖问题近似解的组合优化方法，该方法令取得的解的集合权值之和除以最优解的集合权值之和为“近似率”，令k为所有集合的势的最大值，则该装置取得近似率SHk (取=Eti I)的解的期望步数为mn2，取得近似率为Hk - _的解的期望步数为mk+1n2。

《算法设计与分析》一、 排序和查找是经常遇到的问题。

按照要求完成以下各题：(1)对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。

解：（1）第一步：15 29 135 18 32 1 27 25 5 第二步：29 135 18 32 27 25 15 1 5第三步：135 32 29 18 27 25 15 5 1 第四步：135 32 29 27 25 18 15 5 1(2)请描述递减数组进行二分搜索的基本思想，并给出非递归算法。

解：基本思想：首先将待搜索元素v 与数组的中间元素2n A ⎡⎤⎢⎥⎣⎦进行比较，如果2n v A ⎡⎤>⎢⎥⎣⎦，则在前半部分元素中搜索v ；若2n v A ⎡⎤=⎢⎥⎣⎦，则搜索成功；否则在后半部分数组中搜索v 。

非递归算法：输入：递减数组A[left:right]，待搜索元素v 。

输出：v 在A 中的位置pos ，或者不在A 中的消息（-1）。

步骤：int BinarySearch(int A[],int left,int right,int v) {int mid;while (left<=right) {mid=int((left+right)/2); if (v==A[mid]) return mid;else if (v>A[mid]) right=mid-1; else left=mid+1; }return -1; }(3)给出上述算法的递归算法。

解：输入：递减数组A[left:right]，待搜索元素v 。

输出：v 在A 中的位置pos ，或者不在A 中的消息（-1）。

步骤：【3分】int BinarySearch(int A[],int left,int right,int v) {int mid;if (left<=right){mid=int((left+right)/2); if (v==A[mid]) return mid;else if (v>A[mid]) return BinarySearch(A,left,mid-1,v); else return BinarySearch(A,mid+1,right,v); } elsereturn -1;}(4)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。

高维空间球集覆盖问题是指在$d$ 维欧几里德空间中，找到最小数量的球集合，使得每个点都被至少一个球覆盖。

该问题的近似难度随着维度的增加而增加。

改进的1+ε近似算法可以在$O(dn^{1+\epsilon})$ 的时间内解决该问题，其中$\epsilon$ 是一个小于1 的常数，$n$ 是点集的大小。

算法的基本思想是将所有的点随机映射到一个低维空间，然后使用低维空间的球覆盖来近似原始空间中的球覆盖。

具体来说，算法包括以下步骤：
1.将所有点随机映射到一个$k$ 维空间，其中$k$ 是$d$ 的一个小于$\epsilon^{-1}\ln
n$ 的整数。

可以使用随机正交矩阵或哈希函数来实现随机映射。

2.在$k$ 维空间中找到最小数量的球集合，使得每个点都被至少一个球覆盖。

这个步骤
可以使用常规的贪心算法，例如选取最远点对并覆盖它们之间的所有点。

3.将每个球的半径扩展$\sqrt{\frac{d}{k}}$ 倍，以弥补由于随机映射引入的误差。

4.将每个球映射回原始空间，并将其半径缩小$\sqrt{d}$ 倍。

这个步骤可以通过将球的
中心点映射回原始空间，并将半径乘以$\sqrt{\frac{d}{k}}$ 来实现。

该算法的时间复杂度取决于$k$，通常情况下$k$ 可以选择为$O(\epsilon^{-1}\ln n)$，因此时间复杂度为$O(dn^{1+\epsilon})$。

需要注意的是，该算法仍然存在一些问题，例如它可能会忽略一些小的球，导致最终的覆盖率不够好。

因此，该算法通常只被用作球集覆盖问题的启发式方法。