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

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

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