一种具有中和性的贪污算法

一种具有中和性的贪污算法

最小最大值覆盖问题（pmp）是一个完全pm的问题，不能在多级时间内获得最优解。在p-p的情况下，竞争决策算法（cda）应始终搜索所有剩余点，并找到度值最高的点。每次搜索的规模都会发生变化，最后一次访问的冗余点应检测一下，时间复杂性应达到o（v.4）。混合贪婪算法（mga）提出了解决这个问题的邻接度数的概念，但计算时间差和算法实现过程的复杂性增加了。在这项工作中，我们参考了快速降序算法（fra），使用访问符号号标记节点的方法。即使在同一一轮中标记节点，也不会参与搜索，这大大降低了搜索的范围。换句话说，降低方法中的可变规模算法。该算法消除了相邻长度的概念，直接使用中心长度来完成算法的执行，在一定程度上降低算法的时间性复杂性，并且更容易编程。1相关概念1.1顶及其上覆盖物v#最小顶点覆盖问题是求最少的顶点组成的顶点集,使每条边都至少和其中一个点关联的问题,即给定一个无向简单图G=(V,E),其中V表示顶点的集合,E表示边的集合,求顶点集V的一个最小子集V*,使得任意边e=(u,v)∈E,有u∈V*或v∈V*.也就是说,V*中的顶点覆盖了边集E,顶点覆盖V*的大小是它所包含的顶点个数|V∗|.|V*|.1.2顶集vv和最大值G=(V,E)为无向简单图,其中V为顶点的集合,E为边的集合,a=|V|,b=|E|;A为(a×a)阶的图G的邻接矩阵;P=为初始为空的向量,用于记录所求的最小顶点集;d为根据A求得的顶点集V的度向量;N(v(i))为顶点v(i)的邻点集,N(v(i))={v(j)|(v(i),v(j))∈E};F为顶点集V的标记向量,f(i)=-1表示下标为i的顶点没有被访问过,f(i)=0表示下标为i的顶点已被访问过(1≤i≤a);maxnumd为d中最大的值;[numd,ind]=sorts(d),表示对d按从小到大排序,其中numd表示排序后的度向量,ind表示排序后对应numd中顶点下标值的向量;maxd为numd中标记为-1的最大度数.2算法流程和时间交叉分析2.1fk=-1最大的点对点及最大的顶出值步骤1(初始化)图的邻接矩阵A,顶点的度向量d,以及A的长度a,并把所有顶点的标记置为f(k)=-1(1≤k≤a).步骤2(排序)对度向量d排序,由小到大排序后的度向量为numd,相应顶点的下标向量为ind.步骤3(判断maxnumd)取d中最大的度数maxnumd=numd(a).若maxnumd≥3,则执行步骤3.1;若0<maxnumd<3,则执行步骤3.2;若maxnumd=0,则算法结束.步骤3.1在numd中选择标记f(k)=-1的最大的顶点度数maxd=numd(i).若存在f=-1的点,且maxd≥3,则执行步骤3.1.2,否则执行步骤3.1.1.步骤3.1.1将顶点标记向量F中标记为0的顶点标记变为-1,将ind(a)加入P中,并将v(ind(a))的邻点集N(v(ind(a)))的度数减一.若邻点集N(v(ind(a)))中顶点的度变为0,则置标记为无穷大,否则置为0.将邻接矩阵A中的第ind(a)列和第ind(a)行变为零且将下标为ind(a)顶点的标记变为无穷大.返回步骤2.步骤3.1.2将ind(i)加入P中,并将v(ind(i))邻点集N(v(ind(i)))的度数减一.若邻点集N(v(ind(i)))中顶点的度变为0,则置标记变为无穷大,否则置为0.将邻接矩阵A中的第ind(i)列和第ind(i)行变为零且将下标为ind(i)的顶点的标记变为无穷大.返回步骤2.步骤3.2利用折半查找,在numd中查找度为1的顶点numd(i).如果没找到度为1的点,则执行步骤3.2.1,否则执行步骤3.2.2.步骤3.2.1将ind(a)加入P中,并将v(ind(a))的邻点集N(v(ind(a)))的度数减一;将邻接矩阵A中的第ind(a)列和第ind(a)行变为零;返回步骤2.步骤3.2.2将v(ind(i))的邻点集N(v(ind(i)))中的顶点v(ind(j))的下标ind(j)加入P中;将邻接矩阵A中的第ind(j)列和第ind(j)行变为零;将第ind(i)列和第ind(i)行变为零;返回步骤2.2.2时间复杂度分析步骤3.1寻找标记为-1的最大度数,在最坏情况下的时间复杂度为O(|V|);步骤3.1.1和步骤3.1.2在最坏情况下的时间复杂度均为O(|V|);步骤3.2中折半查找的时间复杂度为O(log|V|);步骤3.2.2寻找v(ind(i))的邻点集N(v(ind(i))),在最坏情况下的时间复杂度为O(|V|).因此,整个算法的在最坏的情况下时间复杂度为O(|V|2).3本方法所含的清度计算方法为了测试算法的执行效果,用MatLab实现了该算法,其主要步骤的伪代码如下:(1)在numd中,选择标记f(k)=-1的最大的顶点度数:fori=a:-1:1ifF(ind(i))==-1maxd=numd(i);break;endh=-1;end其中h用来标记是否找到了f(k)=-1的顶点,若没有找到,则h=-1.(2)该算法的核心部分是步骤3中处理满足条件的顶点的过程,其伪代码如下:将满足条件的顶点的下标ind(i)加入P中,并将与ind(i)相邻的顶点的度减1:P=[P,ind(i)];B=A(ind(i),:);d=d-B;分析与ind(i)相邻的顶点,若其邻接度为0,则将下标所在A中的行列置为0,并将该顶点的标记置为无穷大;若其邻接度不为0,且标记为-1,则将其标记F置为0:forn=a:-1:1ifB(n)～=0ifd(n)==0A(:,n)=0;A(n,:)=0;F(n)=inf;elseifF(n)==-1F(n)=0;endendendend将邻接表中第ind(i)列和第ind(i)行置为0:A(:,ind(i))=0;A(ind(i),:)=0;F(ind(i))=inf;重新计算顶点的度向量d,重新对d进行排序,并将此时度的最大值赋给maxnumd:d=sum(A);[numd,ind]=sort(d);maxnumd=numd(a);(3)在步骤3.2中,利用折半查找,在numd中查找度为1的顶点numd(i),折半查找的代码如下:function[i]=bi_search(s,x,low,high)i=floor(low+(high-low)/2);iflow>highi=-1;return;elseifs(i)==xreturn;elseifs(i)>xi=bi_search(s,x,low,i-1);elseifs(i)<xi=bi_search(s,x,i+1,high);end4实例分析下面以图1所示的简单无向图G=(V,E)为例,来分析算法的过程.(1)初始，点t向量d=，相邻矩阵a的长度a.12，点t的标记向量f=[-1、-1、-1、-1、-1、-1、-1、-1、-1、-1、-1和-1](2)交付向量d[numd,ind]=sorts(d),numd=,ind=[1,2,3,4,5,6,7,8,9,10,11,12].(3)标记为-1的点numd=numd(12)=5.因为maxnumd=5≥3,所以执行步骤3.1;在标记为-1的点中maxd=numd(12)=5≥3,则执行步骤3.1.2:P=[v6],d=,F=[0,-1,0,-1,-1,inf,0,-1,-1,0,0,-1],将A的第6行和第6列变为0.返回步骤2.(4)最大分辨率的测定[numd,ind]=sorts(d),numd=[0,1,1,1,1,1,2,2,2,2,2,3],ind=[1,2,3,4,5,6,7,8,9,10,11,12].取d中最大的度数maxnumd=numd(12)=3,执行步骤3.1;在标记为-1的点中maxd=numd(10)=2≤2,则执行步骤3.1.1:F=[-1,-1,-1,-1,-1,inf,-1,-1,-1,-1,-1,-1],P=[v6,v7],d=,F=[-1,-1,inf,-1,-1,inf,inf,-1,-1,-1,inf,inf],将A的第7行和第7列变为0.返回步骤2.(5)umd,ind[numd,ind]=sorts(d),numd=[0,0,0,0,0,1,1,2,2,2,2,2],ind=[1,2,3,4,5,6,7,8,9,10,11,12].(6)清阶层中降压机型前5位的前置表2.2.2.2.2.2.2.2numd=numd(12)=2,执行步骤3.2:在numd中,利用折半查找,查找度为1的顶点numd(i).因查找到了numd(6)=1,所以执行步骤3.2.2:P=[v6,v7,v8],d=,将A的第8行和第8列及第4行和第4列变为0.返回步骤2.(7)umd,ind[numd,ind]=sorts(d),numd=[0,0,0,0,0,0,0,2,2,2,2,2],ind=[1,2,3,4,5,6,7,8,9,10,11,12].(8)点世界i在numd中,利用折半查找,查找度为1的顶点numd(i).因没有查到,所以执行步骤3.2.1:P=[v6,v7,v8,v10],d=,将A的第10行和第10列.返回步骤2.(9)umd、ind的计算[numd,ind]=sorts(d),numd=[0,0,0,0,0,0,0,0,1,1,2,2],ind=[1,2,3,4,5,6,7,8,9,10,11,12].(10)把中国的前3位纳入独立的前置条件,把a在numd中,利用折半查找,查找度为1的顶点numd(i).因查找到了numd(9)=1,所以执行步骤3.2.2:P=[v6,v7,v8,v10,v2],d=,将A的第2行和第2列及第5行和第5列变为0.返回步骤2.(11)umd、ind的计算[numd,ind]=sorts(d),numd=[0,0,0,0,0,0,0,0,0,0,1,1],ind=[1,2,3,4,5,6,7,8,9,10,11,12].(12)a.寻找非整合性的点对点numd=numd(12)=1,执行步骤3.2:在numd中,利用折半查找,查找度为1的顶点numd(i).因查找到了numd(11)=1,所以执行步骤3.2.2:P=[v6,v7,v8,v10,v2,v9],d=[0,0,0,0,0,0,0,0,1,0,0,0],将A的第1行和第1列及第9行和第9列变为0.返回步骤2.(13)umd、ind的计算[numd,ind]=sorts(d),numd=[0,0,0,0,0,0,0,0,0,0,0,0],ind=[1,2,3,4,5,6,7,8,9,10,11,12].(14)以现有的算法为中心的中和性求解算法numd=numd(12)=0,则算法结束,即最小顶点集为P=[v6,v7,v8,v10,v2,v9].综上所述,本文给出的算法通过对求解图的MVC