一種具有中和性的貪污算法

最小最大值覆蓋問(wèn)題（pmp）是一個(gè)完全pm的問(wèn)題，不能在多級(jí)時(shí)間內(nèi)獲得最優(yōu)解。在p-p的情況下，競(jìng)爭(zhēng)決策算法（cda）應(yīng)始終搜索所有剩余點(diǎn)，并找到度值最高的點(diǎn)。每次搜索的規(guī)模都會(huì)發(fā)生變化，最后一次訪問(wèn)的冗余點(diǎn)應(yīng)檢測(cè)一下，時(shí)間復(fù)雜性應(yīng)達(dá)到o（v.4）。混合貪婪算法（mga）提出了解決這個(gè)問(wèn)題的鄰接度數(shù)的概念，但計(jì)算時(shí)間差和算法實(shí)現(xiàn)過(guò)程的復(fù)雜性增加了。在這項(xiàng)工作中，我們參考了快速降序算法（fra），使用訪問(wèn)符號(hào)號(hào)標(biāo)記節(jié)點(diǎn)的方法。即使在同一一輪中標(biāo)記節(jié)點(diǎn)，也不會(huì)參與搜索，這大大降低了搜索的范圍。換句話(huà)說(shuō)，降低方法中的可變規(guī)模算法。該算法消除了相鄰長(zhǎng)度的概念，直接使用中心長(zhǎng)度來(lái)完成算法的執(zhí)行，在一定程度上降低算法的時(shí)間性復(fù)雜性，并且更容易編程。1相關(guān)概念1.1頂及其上覆蓋物v#最小頂點(diǎn)覆蓋問(wèn)題是求最少的頂點(diǎn)組成的頂點(diǎn)集,使每條邊都至少和其中一個(gè)點(diǎn)關(guān)聯(lián)的問(wèn)題,即給定一個(gè)無(wú)向簡(jiǎn)單圖G=(V,E),其中V表示頂點(diǎn)的集合,E表示邊的集合,求頂點(diǎn)集V的一個(gè)最小子集V*,使得任意邊e=(u,v)∈E,有u∈V*或v∈V*.也就是說(shuō),V*中的頂點(diǎn)覆蓋了邊集E,頂點(diǎn)覆蓋V*的大小是它所包含的頂點(diǎn)個(gè)數(shù)|V?|.|V*|.1.2頂集vv和最大值G=(V,E)為無(wú)向簡(jiǎn)單圖,其中V為頂點(diǎn)的集合,E為邊的集合,a=|V|,b=|E|;A為(a×a)階的圖G的鄰接矩陣;P=為初始為空的向量,用于記錄所求的最小頂點(diǎn)集;d為根據(jù)A求得的頂點(diǎn)集V的度向量;N(v(i))為頂點(diǎn)v(i)的鄰點(diǎn)集,N(v(i))={v(j)|(v(i),v(j))∈E};F為頂點(diǎn)集V的標(biāo)記向量,f(i)=-1表示下標(biāo)為i的頂點(diǎn)沒(méi)有被訪問(wèn)過(guò),f(i)=0表示下標(biāo)為i的頂點(diǎn)已被訪問(wèn)過(guò)(1≤i≤a);maxnumd為d中最大的值;[numd,ind]=sorts(d),表示對(duì)d按從小到大排序,其中numd表示排序后的度向量,ind表示排序后對(duì)應(yīng)numd中頂點(diǎn)下標(biāo)值的向量;maxd為numd中標(biāo)記為-1的最大度數(shù).2算法流程和時(shí)間交叉分析2.1fk=-1最大的點(diǎn)對(duì)點(diǎn)及最大的頂出值步驟1(初始化)圖的鄰接矩陣A,頂點(diǎn)的度向量d,以及A的長(zhǎng)度a,并把所有頂點(diǎn)的標(biāo)記置為f(k)=-1(1≤k≤a).步驟2(排序)對(duì)度向量d排序,由小到大排序后的度向量為numd,相應(yīng)頂點(diǎn)的下標(biāo)向量為ind.步驟3(判斷maxnumd)取d中最大的度數(shù)maxnumd=numd(a).若maxnumd≥3,則執(zhí)行步驟3.1;若0<maxnumd<3,則執(zhí)行步驟3.2;若maxnumd=0,則算法結(jié)束.步驟3.1在numd中選擇標(biāo)記f(k)=-1的最大的頂點(diǎn)度數(shù)maxd=numd(i).若存在f=-1的點(diǎn),且maxd≥3,則執(zhí)行步驟3.1.2,否則執(zhí)行步驟3.1.1.步驟3.1.1將頂點(diǎn)標(biāo)記向量F中標(biāo)記為0的頂點(diǎn)標(biāo)記變?yōu)?1,將ind(a)加入P中,并將v(ind(a))的鄰點(diǎn)集N(v(ind(a)))的度數(shù)減一.若鄰點(diǎn)集N(v(ind(a)))中頂點(diǎn)的度變?yōu)?,則置標(biāo)記為無(wú)窮大,否則置為0.將鄰接矩陣A中的第ind(a)列和第ind(a)行變?yōu)榱闱覍⑾聵?biāo)為ind(a)頂點(diǎn)的標(biāo)記變?yōu)闊o(wú)窮大.返回步驟2.步驟3.1.2將ind(i)加入P中,并將v(ind(i))鄰點(diǎn)集N(v(ind(i)))的度數(shù)減一.若鄰點(diǎn)集N(v(ind(i)))中頂點(diǎn)的度變?yōu)?,則置標(biāo)記變?yōu)闊o(wú)窮大,否則置為0.將鄰接矩陣A中的第ind(i)列和第ind(i)行變?yōu)榱闱覍⑾聵?biāo)為ind(i)的頂點(diǎn)的標(biāo)記變?yōu)闊o(wú)窮大.返回步驟2.步驟3.2利用折半查找,在numd中查找度為1的頂點(diǎn)numd(i).如果沒(méi)找到度為1的點(diǎn),則執(zhí)行步驟3.2.1,否則執(zhí)行步驟3.2.2.步驟3.2.1將ind(a)加入P中,并將v(ind(a))的鄰點(diǎn)集N(v(ind(a)))的度數(shù)減一;將鄰接矩陣A中的第ind(a)列和第ind(a)行變?yōu)榱?返回步驟2.步驟3.2.2將v(ind(i))的鄰點(diǎn)集N(v(ind(i)))中的頂點(diǎn)v(ind(j))的下標(biāo)ind(j)加入P中;將鄰接矩陣A中的第ind(j)列和第ind(j)行變?yōu)榱?將第ind(i)列和第ind(i)行變?yōu)榱?返回步驟2.2.2時(shí)間復(fù)雜度分析步驟3.1尋找標(biāo)記為-1的最大度數(shù),在最壞情況下的時(shí)間復(fù)雜度為O(|V|);步驟3.1.1和步驟3.1.2在最壞情況下的時(shí)間復(fù)雜度均為O(|V|);步驟3.2中折半查找的時(shí)間復(fù)雜度為O(log|V|);步驟3.2.2尋找v(ind(i))的鄰點(diǎn)集N(v(ind(i))),在最壞情況下的時(shí)間復(fù)雜度為O(|V|).因此,整個(gè)算法的在最壞的情況下時(shí)間復(fù)雜度為O(|V|2).3本方法所含的清度計(jì)算方法為了測(cè)試算法的執(zhí)行效果,用MatLab實(shí)現(xiàn)了該算法,其主要步驟的偽代碼如下:(1)在numd中,選擇標(biāo)記f(k)=-1的最大的頂點(diǎn)度數(shù):fori=a:-1:1ifF(ind(i))==-1maxd=numd(i);break;endh=-1;end其中h用來(lái)標(biāo)記是否找到了f(k)=-1的頂點(diǎn),若沒(méi)有找到,則h=-1.(2)該算法的核心部分是步驟3中處理滿(mǎn)足條件的頂點(diǎn)的過(guò)程,其偽代碼如下:將滿(mǎn)足條件的頂點(diǎn)的下標(biāo)ind(i)加入P中,并將與ind(i)相鄰的頂點(diǎn)的度減1:P=[P,ind(i)];B=A(ind(i),:);d=d-B;分析與ind(i)相鄰的頂點(diǎn),若其鄰接度為0,則將下標(biāo)所在A中的行列置為0,并將該頂點(diǎn)的標(biāo)記置為無(wú)窮大;若其鄰接度不為0,且標(biāo)記為-1,則將其標(biāo)記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;重新計(jì)算頂點(diǎn)的度向量d,重新對(duì)d進(jìn)行排序,并將此時(shí)度的最大值賦給maxnumd:d=sum(A);[numd,ind]=sort(d);maxnumd=numd(a);(3)在步驟3.2中,利用折半查找,在numd中查找度為1的頂點(diǎn)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實(shí)例分析下面以圖1所示的簡(jiǎn)單無(wú)向圖G=(V,E)為例,來(lái)分析算法的過(guò)程.(1)初始，點(diǎn)t向量d=，相鄰矩陣a的長(zhǎng)度a.12，點(diǎn)t的標(biāo)記向量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)標(biāo)記為-1的點(diǎn)numd=numd(12)=5.因?yàn)閙axnumd=5≥3,所以執(zhí)行步驟3.1;在標(biāo)記為-1的點(diǎn)中maxd=numd(12)=5≥3,則執(zhí)行步驟3.1.2:P=[v6],d=,F=[0,-1,0,-1,-1,inf,0,-1,-1,0,0,-1],將A的第6行和第6列變?yōu)?.返回步驟2.(4)最大分辨率的測(cè)定[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中最大的度數(shù)maxnumd=numd(12)=3,執(zhí)行步驟3.1;在標(biāo)記為-1的點(diǎn)中maxd=numd(10)=2≤2,則執(zhí)行步驟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列變?yōu)?.返回步驟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)清階層中降壓機(jī)型前5位的前置表2.2.2.2.2.2.2.2numd=numd(12)=2,執(zhí)行步驟3.2:在numd中,利用折半查找,查找度為1的頂點(diǎn)numd(i).因查找到了numd(6)=1,所以執(zhí)行步驟3.2.2:P=[v6,v7,v8],d=,將A的第8行和第8列及第4行和第4列變?yōu)?.返回步驟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)點(diǎn)世界i在numd中,利用折半查找,查找度為1的頂點(diǎn)numd(i).因沒(méi)有查到,所以執(zhí)行步驟3.2.1:P=[v6,v7,v8,v10],d=,將A的第10行和第10列.返回步驟2.(9)umd、ind的計(jì)算[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)把中國(guó)的前3位納入獨(dú)立的前置條件,把a(bǔ)在numd中,利用折半查找,查找度為1的頂點(diǎn)numd(i).因查找到了numd(9)=1,所以執(zhí)行步驟3.2.2:P=[v6,v7,v8,v10,v2],d=,將A的第2行和第2列及第5行和第5列變?yōu)?.返回步驟2.(11)umd、ind的計(jì)算[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.尋找非整合性的點(diǎn)對(duì)點(diǎn)numd=numd(12)=1,執(zhí)行步驟3.2:在numd中,利用折半查找,查找度為1的頂點(diǎn)numd(i).因查找到了numd(11)=1,所以執(zhí)行步驟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列變?yōu)?.返回步驟2.(13)umd、ind的計(jì)算[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)以現(xiàn)有的算法為中心的中和性求解算法numd=numd(12)=0,則算法結(jié)束,即最小頂點(diǎn)集為P=[v6,v7,v8,v10,v2,v9].綜上所述,本文給出的算法通過(guò)對(duì)求解圖的MVC