最大覆盖问题研究

龙源期刊网最大覆盖问题研究作者：王翰来源：《科技传播》2011年第22期摘要最大覆盖问题是运筹学中一个经典组合优化问题。通常是现实生活中邮政服务站点，加油站点，银行选址等问题的数学抽象。最大覆盖问题一般被描述为有被服务点若干，选取若干服务点对被服务点进行服务的最小代价。最大覆盖问题已经被证明是一类NP问题，也就是不能在多项式时间内求得最优值的问题。目前国内外学者对于此问题的研究多是使用遗传，蚁群，退火模拟等启发式搜索求的近似值的方法来进行讨论。本文主要分析了最大覆盖问题的穷举解法，剪枝搜索解法和启发式搜索解法。对这三种解法进行了测试，比较算法的优劣和适用范围。通过提出对于待选边进行性价比的计算，设计出启发式函数来搜索近似最优值，最后的测试将近似最优值保持在平均2的差异值范围内。关键词最大覆盖问题；穷举解法；剪枝搜索解法；启发式搜索解法中图分类号TP39文献标识码A文章编号1674-6708（2011）55-0218-021问题描述1.1具体问题最大覆盖问题是现实生活中对邮政站点，加油站点，银行等一系列选址问题的数学抽象。一般被描述为有被服务点若干，选取若干服务点对被服务点进行服务的最小代价。1.2数学描述通常最大覆盖问题可以通过矩阵覆盖问题来简化为数学抽象问题，即最大覆盖问题中，Am*n是一个M*N二维矩阵，其中aij表示j列是否覆盖i行。aij=0表示j列不覆盖i行，aij=1表示j列覆盖i行。Cn数组维护列的代价，Cj表示选择j列的代价。目标解为Z，Zj=0表示j列未被选中，Zj=1表示j列被选中。目标解为:minj*Cj解约束条件为:j*aij=1,i=1,2,3…mZj∈{0,1},j=1,2,3….n龙源期刊网*n矩阵00100001101001011010Cn3212由于Zj∈{0,1}j=1,2,3…n。这个解的空间是2n，随着n的增大，计算机在有限时间内很难通过穷举得出最优解，计算近似解是解决这类NP问题的常用方法。如上面例子Am*n矩阵，Cn为列代价值。那么Z={0,0,1,1}是这个矩阵的最优解，代价为3且覆盖所有的行。2剪枝搜索2.1算法描述通常搜索全局的解可以在某些时候剪去一些不可能出现最优解的子树，从而达到计算速度上的提升。最简单的剪枝方法就是在选择列的时候进行如下判断：设想当目前选择的Z已经超过了minCost值的时候，它的任何子局面都不可能出现比minCost小的解，所以目前这个Z局面以及它的所有子局面都应该被剪掉。也就是说此列在之前选择列集合的前提下不应该被选中。2.2求解步骤这里实现剪枝的方法是用递归的形式Search(index,cost)//index表示选择到多少列了，cost表示当前总共选择的代价{If(index等于n)//选择完成{龙源期刊网(coverAll&&cost{minCost=cost;}返回}//如果取当前index列的总共代价//小于minCost则继续搜索if(cost+C[index]search(++index,cost+C[index]);}//不取index列的所有解Z[index]=0;search(++index,cost);}单纯通过剪枝的算法可以加速搜索，通常效果明显，解也是最优的，不过复杂度其实还是2n，因为在最坏情况下，剪枝实际上还是会搜索整个树。3启发式搜索3.1算法描述近似求解是对最大覆盖问题在有限时间内得到解的有效解法。通常可以通过设置启发式的搜索有选择的对子节点进行计算，评估当前的所有子节点找出最有可能出现最优情况的若干子节点进行搜索。针对最大覆盖问题，设当某一时刻，对于所有未被覆盖的行和未选择的列进行覆盖率计算，即j列能覆盖到的未覆盖行数count,取value=count/C[j].这意味着选择j列的性价比值，通过对于value的排序可以得到一个对接下来选择列的优先权。可以通过选取value最大的j来完成对层的搜索，从而跳到下一层。为了使其跳离局部最优，可以取value的前N个作为当层的解再往下选择。龙源期刊网[N]//j列覆盖未覆盖行数/j列的costintisCover[M]//当前i行是否被覆盖intisChoice[N]//当前j列是否被选择doublemin=MAXvoidSearch(cost){If(isCoverallis1&&cost{min=cost;打印min//近似最优打印isChoice数组//选择结果return}//更新performanceFor(inti=0;i{If(isChoice[i]==1){Performance[i]=0;龙源期刊网}//对于没有选择的列，//计算valuePerformance[i]=j列覆盖率/C[j]}//选择前N大performance//k,k+1,k+2…k+nFor(所有选择的列){更新isCover更新isChoiceSearch(cost+choiceCost)还原isCover还原isChoice}}近似解法就是通过中间评估函数，对于备选点进行筛选，从而很快的靠近最优解。可以在有限时间内解决NP问题4实验结果我们可以通过更大数据量的测试来看出剪枝和启发式搜索的性能和运算结果的比较。如下表：龙源期刊网*2522小于15ms22小于15ms0%200*5018小于15ms1416ms4300*7512小于15ms1178ms1400*10011小于15ms9297ms2500*12510小于15ms9515ms1600*150916ms81484ms1700*175815ms71703ms1800*200931ms85094ms1900*225816ms822437ms01000*250831ms76109ms1上表可以看到，启发式搜索随着矩阵的规模变化，计算时间没有显著提高，而剪枝搜索在矩阵达到1000的规模时候时间增加了千倍。同时启发式搜索的差异值始终保持在1左右，这组测试数据的平均差异值为1.2。5结论至此，我们看到，启发式搜索在对待处理节点进行性价比的判断，从而有方向性的选取可能出现最优解的子树，快速收敛到比较小的值。但是这个值可能是局部最优值。这里我们可以对启发式进行一些处理来避免局部最优解的出现，就是在选取子树的时候进行多个可能的子节点选取。通常是性价比值最大的前K个子节点，这样找到最优解的概率就更大，当然需要的时间也会增加，但是算法的复杂度已经不再是2的n次方，而是多项式的复杂度了。这样启发式的搜索就可以处理n为亿次数量级的覆盖问题。参考文献龙源期刊网[1]Christofides,N.,andEilon,S.,Algorithmsforlargescaletravellingsalesmanproblems,OperationalResearchQuarterly23(1972)511-518.[2]Church,R.L.,andReVelle,C.S.,Themaximalcoveringlocationproblem,PapersoftheRegionalScienceAssociation32(1974)101-118.[3]Church,R.L.,Current,J.,andStorbeck,J.,Abicriterionmaximalcoveringlocationformulationwhichconsidersthesatisfactionofuncovereddemand,DecisionSciences22(1991)38-52.[4]Eilon,S.,andGalvfio,R.D.,Singleanddoublevertexsubstitutioninheuristicproceduresforthep-medianproblem,ManagementScience24(1978)1763-1766.[5]Garfinkel,R.S.,Neebe,A.W.,andRao,M.R.,Analgorithmforthem-medianplantlocationproblem,TransportationScience8(1974)217-236.[6]Kerningan,B.W.,andLin,S.,Anefficientheuristicprocedureforpartitioninggraphs,BellSystemTechnicalJournal49(1970)291-307.[7]Lin,S.,Computersolutionsofthetravellingsalesmanproblem,BellSystemTechnicalJournal44(1965)2245-2269.