亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        集合覆蓋問題降階算法

        2012-03-22 02:20:58寧愛兵劉艷芳王英磊
        關(guān)鍵詞:降階下界子集

        寧愛兵, 劉艷芳, 王英磊

        (上海理工大學(xué)管理學(xué)院,上海 200093)

        集合覆蓋問題(set covering problem,SCP)是組合優(yōu)化中一個(gè)典型NP(non-deterministic polynomial time,非確定多項(xiàng)式時(shí)間算法)難解問題,是計(jì)算機(jī)和運(yùn)籌學(xué)中的一個(gè)經(jīng)典問題,在人員調(diào)動(dòng)、網(wǎng)絡(luò)安全、資源分配、電路設(shè)計(jì)、運(yùn)輸車輛路徑安排等領(lǐng)域有著廣泛的應(yīng)用[1-4].

        對(duì)于集合覆蓋問題,目前國(guó)內(nèi)外主要有兩種處理方法:一種是采用啟發(fā)式算法[2-3];另外一種是采用精確算法或近似算法[1,4].各種算法的優(yōu)缺點(diǎn)及其對(duì)比將在后面介紹.

        本文將集合覆蓋問題轉(zhuǎn)換成二分圖,再在二分圖上給出降階規(guī)則,給出上界和下界子算法,最后結(jié)合成一個(gè)新的降階算法.

        1 問題及算法介紹

        1.1 問題簡(jiǎn)介

        集合覆蓋問題是一個(gè)優(yōu)化問題,其原型是多資源選擇問題.集合覆蓋問題可以看作是圖的頂點(diǎn)覆蓋問題的推廣,它也是一個(gè)NP難問題.

        集合覆蓋問題的一個(gè)實(shí)例〈X,F(xiàn)〉由一個(gè)有限集X及X的一個(gè)子集族F組成.子集族F覆蓋了有限集X,也就是說X中每一元素至少屬于F中的一個(gè)子集,即對(duì)于F中的一個(gè)子集C?F,若C中的X的子集覆蓋了X,即,則稱C覆蓋了X.集合覆蓋問題就是要找出F中覆蓋X的最小子集C*,使得|C*|=min{|C‖C?F且C覆蓋X}.

        1.2 問題轉(zhuǎn)換

        在算法處理之前,將該問題轉(zhuǎn)換成二分圖來進(jìn)行處理,轉(zhuǎn)換方法如下:

        將集合覆蓋問題〈X,F(xiàn)〉中X的每個(gè)元素作為二分圖的一個(gè)頂點(diǎn)子集X,把F中的每個(gè)元素作為二分圖的另一個(gè)頂點(diǎn)子集F,F(xiàn)中的元素是集合.若F中的元素f1包含X中的元素x1,則在f1與x1之間連線,否則不連線.

        這樣處理后,得到一個(gè)圖G=(V,E),其中,V=X∪F,E={(x,f)|x∈X,f∈F且x∈f}.很顯然,圖G是二分圖.而原問題的求解變?yōu)樵陧旤c(diǎn)子集F中找出一個(gè)最小的子集C*,使得頂點(diǎn)子集X中的每一個(gè)頂點(diǎn)至少與C*中的頂點(diǎn)有一條邊相連.

        1.3 數(shù)學(xué)符號(hào)

        為了方便描述,除了問題簡(jiǎn)介和問題轉(zhuǎn)換中定義的符號(hào)外,還定義如下符號(hào):

        n表示二分圖G中頂點(diǎn)集X中結(jié)點(diǎn)的個(gè)數(shù);

        m表示二分圖G中頂點(diǎn)集F中結(jié)點(diǎn)的個(gè)數(shù);

        d(vi)表示結(jié)點(diǎn)vi的度,其值為與vi關(guān)聯(lián)邊的條數(shù);

        N(vi)表示二分圖中頂點(diǎn)vi的鄰點(diǎn)集,N(vi)={vj|(vi,vj)∈E};

        Φ表示空集;

        b表示最小覆蓋子集C*中元素個(gè)數(shù)的下界,即|C*|≥b;

        u表示最小覆蓋子集C*中元素個(gè)數(shù)的上界,即|C*|≤u.

        1.4 下界子算法

        對(duì)X中的元素xi,由于必須至少有1個(gè)集合覆蓋它,也就是說C*中至少有1個(gè)結(jié)點(diǎn)要與它關(guān)聯(lián),因此N(xi)至少有1個(gè)結(jié)點(diǎn)在C*中,故有下面的下界子算法.

        a.i=1;

        b.集合temp_c=Φ;

        c.若i>n或者temp_c中元素的數(shù)量為m,則整個(gè)算法結(jié)束并得到下界b;

        d.對(duì)X中的元素xi,若N(xi)∩temp_c=Φ,則i=i+1,b=b+1,temp_c=N(xi)∪temp_c并跳至第c步,否則執(zhí)行i=i+1并跳至第c步.

        算法中的N(xi)∩temp_c=Φ說明目前還沒有集合覆蓋xi.

        1.5 上界子算法

        采用如下貪心算法求解上界u:

        a.令G2為待處理的二分圖,X2=X,F(xiàn)2=F;

        b.u=0,集合temp_c=Φ;

        c.若X2為空集,則算法結(jié)束,否則跳至第d步;

        d.在F2中找出1個(gè)度最大的結(jié)點(diǎn)f1,其中f1∈F2;

        e.u=u+1,temp_c=temp_c∪{f1},在二分圖G2中刪除結(jié)點(diǎn)f1及其關(guān)聯(lián)邊,F(xiàn)2=F2-{f1},刪除集合N(f1)中的結(jié)點(diǎn)及其關(guān)聯(lián)邊,X2=X2-N(f1),修改對(duì)應(yīng)結(jié)點(diǎn)的d(vi),跳到第c步.

        該子算法對(duì)圖的刪除操作都是在臨時(shí)變量圖G2中進(jìn)行的,不影響原來的二分圖.

        1.6 降階規(guī)則

        規(guī)則1 對(duì)頂點(diǎn)集X中度為1的結(jié)點(diǎn)xi,其關(guān)聯(lián)邊對(duì)應(yīng)的另一個(gè)結(jié)點(diǎn)fj一定在最小子集C*中.

        證明 因?yàn)槎葹?的結(jié)點(diǎn)xi必須被某個(gè)集合覆蓋,而xi僅僅只屬于一個(gè)集合fj,故要覆蓋xi,則fj一定在最小子集C*中.

        規(guī)則2 對(duì)頂點(diǎn)集F中的兩個(gè)元素f1和f2,若N(f1)?N(f2),則可以將頂點(diǎn)f1及其關(guān)聯(lián)邊從圖中刪除而不會(huì)影響最小的子集C*求解.

        證明 因?yàn)镹(f1)?N(f2),所以f1所起到的覆蓋作用完全可以由f2來代替.代替后的覆蓋功能只會(huì)更強(qiáng),而不會(huì)更弱,而目標(biāo)函數(shù)最小子集C*中的數(shù)量不變.因此可以把頂點(diǎn)f1及其關(guān)聯(lián)邊從圖中刪除而不會(huì)影響最小子集C*求解.

        在降階的中間過程中,可能會(huì)出現(xiàn)度為0的結(jié)點(diǎn),也可能在F中存在1個(gè)能覆蓋X中所有結(jié)點(diǎn)的子集合f1,此時(shí)采用規(guī)則3和規(guī)則4來降階.

        規(guī)則3 在降階的任何過程中,可以將頂點(diǎn)集F中度為0的結(jié)點(diǎn)f1直接從圖中刪除.

        證明 由于頂點(diǎn)集F中度為0的結(jié)點(diǎn)f1不能覆蓋任何結(jié)點(diǎn),因此可以直接刪除.

        規(guī)則4 在降階的任何過程中,若頂點(diǎn)集F中存在一個(gè)結(jié)點(diǎn)f1覆蓋X中的所有結(jié)點(diǎn),則將f1加入到最小子集C*中.

        證明 由于此時(shí)X中還有結(jié)點(diǎn)沒有被覆蓋,故至少需要在F中找出一個(gè)子集合來覆蓋,而能在F中找到一個(gè)能覆蓋X中的所有結(jié)點(diǎn)的子集合f1,則可以將f1加入到最小子集C*中.

        其它的降階方法在后面的算法中介紹.

        1.7 降階算法

        對(duì)于已經(jīng)轉(zhuǎn)成二分圖的問題,采用如下算法進(jìn)行降階:

        a.下界b=0,C*=Φ;

        b.調(diào)用下界子算法求出下界b;

        c.按照規(guī)則1,對(duì)于X中度為1的結(jié)點(diǎn)xi,把其關(guān)聯(lián)邊對(duì)應(yīng)的另一個(gè)結(jié)點(diǎn)fj加到最小子集C*中,b=b-1,并把結(jié)點(diǎn)xi及其關(guān)聯(lián)邊從圖中刪除.將結(jié)點(diǎn)fj、結(jié)點(diǎn)集合N(fj)及其關(guān)聯(lián)邊從圖中刪除,并修改對(duì)應(yīng)點(diǎn)的度d(vi),修改變量n和m.這樣持續(xù)做下去,直到X中不存在度為1的結(jié)點(diǎn)為止;

        d.按照規(guī)則2,對(duì)頂點(diǎn)集F中的兩個(gè)元素f1和f2,若N(f1)?N(f2),則可以把頂點(diǎn)f1及其關(guān)聯(lián)邊從圖中刪除并修改對(duì)應(yīng)點(diǎn)的度d(vi),同時(shí)修改變量m;

        e.若d中刪除過結(jié)點(diǎn),則跳到第c步,否則執(zhí)行下一步;

        f.采用規(guī)則3和規(guī)則4來降階,調(diào)用上界子算法求出上界u,若此時(shí)u=b,則令C1為上界子算法中的temp_c,此時(shí)C*=C*∪C1為最優(yōu)解,整個(gè)算法結(jié)束;

        g.j=0;

        h.若j>m,則跳到第o步;

        i.對(duì)F中的元素fj,令N2(fj)為N(fj)中度為2的結(jié)點(diǎn)集合,若N2(fj)中結(jié)點(diǎn)數(shù)量大于等于u,則執(zhí)行下一步,否則跳到第n步;

        j.集合temp_c=Φ;

        k.把N2(fj)中每一個(gè)結(jié)點(diǎn)vi的鄰點(diǎn)集N(vi)加到集合temp_c中;

        l.temp_c=temp_c-fj(這里操作的含義是假設(shè)fj不在最小子集C*中);

        m.若temp_c的數(shù)量大于u,則把結(jié)點(diǎn)fj加到最小子集C*中,把結(jié)點(diǎn)fj和結(jié)點(diǎn)集合N(fj)從圖中刪除,同時(shí)執(zhí)行m=m-1,n=n-|N(fj)|,u=u-1,并修改對(duì)應(yīng)點(diǎn)的度;

        n.采用規(guī)則3和規(guī)則4來降階;j=j(luò)+1,跳到第h步;

        o.若在第h至n步中刪除過結(jié)點(diǎn),則跳到第c步,否則整個(gè)算法結(jié)束.此時(shí)C*中的元素是在最小集合覆蓋中的元素,若此時(shí)圖為無邊的空?qǐng)D,則得到最小集合覆蓋C*,否則說明只是降低了問題的規(guī)模和難度,但沒有得到最終的最優(yōu)解.

        算法中的第i到第l步是利用反證法降階,即假設(shè)fj不在最小集合覆蓋C*中時(shí),若能判斷此時(shí)要加入到C*的元素個(gè)數(shù)大于上界u,則說明出現(xiàn)矛盾,因此fj一定在最小集合覆蓋C*中.

        1.8 算法的時(shí)間復(fù)雜度分析

        下面的分析,都是指在最壞情況下的時(shí)間復(fù)雜度.

        問題轉(zhuǎn)換的時(shí)間復(fù)雜度為O(nm),下界子算法為O(nm2),上界子算法為O(nm),降階算法的第c步為O(n),第d步為O(n2m2),第h步到第n步為O(n2m),因此整個(gè)算法的時(shí)間復(fù)雜度為O(n2m3).

        2 示例分析

        為了更清楚地了解算法的原理及應(yīng)用情況,下面給出3個(gè)示例來進(jìn)行分析.

        示例1 求圖1(見下頁)中圖G的最小集合覆蓋,其中,X={a,b,c,d,e,f,g,h,i,j,k,l},F(xiàn)={s1,s2,s3,s4,s5,s6},s1={a,b,e,f,i,j},s2={f,g,j,k},s3={a,b,c,d},s4={e,f,g,h},s5={i,j,k,l},s6={d,h},該示例取自文獻(xiàn)[1],文獻(xiàn)[1]提供的近似算法.

        分析方法一:

        Step 1 先把圖1轉(zhuǎn)成如圖2(見下頁)所示的二分圖;

        圖1 示例1Fig.1 Instance 1

        圖2 二分圖Fig.2 Bipartite graph

        Step 2 調(diào)用下界子算法求出下界b=3;

        Step 3 按照規(guī)則1,對(duì)于X中度為1的結(jié)點(diǎn)l,將其關(guān)聯(lián)邊對(duì)應(yīng)的另一個(gè)結(jié)點(diǎn)s5加到最小子集C*中,得C*={s5},b=b-1=2,并將結(jié)點(diǎn)l及其關(guān)聯(lián)邊從圖中刪除,把結(jié)點(diǎn)s5、結(jié)點(diǎn)集N(s5)及其關(guān)聯(lián)邊從圖中刪除,并修改對(duì)應(yīng)點(diǎn)的度d(vi),修改變量n=8和m=5,得到圖3所示的圖形;

        圖3 二分圖Fig.3 Bipartite graph

        Step 4 按照規(guī)則2,對(duì)頂點(diǎn)集F中的兩個(gè)元素s2和s4,由于N(s2)?N(s4),所以可以將頂點(diǎn)s2及其關(guān)聯(lián)邊從圖中刪除并修改對(duì)應(yīng)點(diǎn)的度d(vi),同時(shí)修改變量m=5-1=4,得到圖4所示的圖形;

        Step 5 按照規(guī)則1,對(duì)于X中度為1的結(jié)點(diǎn)g,把其關(guān)聯(lián)邊對(duì)應(yīng)的另一個(gè)結(jié)點(diǎn)s4加到最小子集C*中,得C*={s4,s5},b=b-1=1,并將結(jié)點(diǎn)g及其關(guān)聯(lián)邊從圖中刪除,把結(jié)點(diǎn)s4、結(jié)點(diǎn)N(s4)及其關(guān)聯(lián)邊從圖中刪除,并修改對(duì)應(yīng)點(diǎn)的度d(vi),修改變量n=3和m=3,得到圖5所示的圖形;

        圖4 二分圖Fig.4 Bipartite graph

        圖5 二分圖Fig.5 Bipartite graph

        Step 6 執(zhí)行算法的第f步,求得上界u=1,此時(shí)u=b,得到最優(yōu)解C*={s3,s4,s5},整個(gè)算法結(jié)束.

        分析方法二:

        為了演示降階算法中的第h到第n步,下面不使用規(guī)則2來降階,也不使用算法第f步中的u=b的方法來降階.

        這里的第1,2,3步同分析方法一中的完全相同,此時(shí)得到圖3所示的圖形.

        Step 7 執(zhí)行算法的第f步,求得上界u=2;

        Step 8 執(zhí)行算法的第i步,對(duì)F中的元素s3,N2(s3)={a,b,c,d}為N(s3)中度為2的結(jié)點(diǎn)集合,由于N2(s3)中結(jié)點(diǎn)數(shù)量大于等于u,則跳到算法的第j步;

        Step 9 執(zhí)行算法的第j步,集合temp_c=Φ;

        Step 10 執(zhí)行算法的第k步,將N2(s3)={a,b,c,d}中每個(gè)結(jié)點(diǎn)vi的鄰點(diǎn)集N(vi)加到集合temp_c中,得temp_c={s1,s3,s4,s6};

        Step 11 執(zhí)行算法的第l步,得temp_c=temp_c-fi={s1,s4,s6}

        Step 12 執(zhí)行算法的第m步,C*={s3,s5},將結(jié)點(diǎn)s3、結(jié)點(diǎn)集N(s3)從圖中刪除,m=m-1=4,n=4,u=u-1=1,得到圖6;

        Step 13 執(zhí)行算法的第n步,采用規(guī)則4來降階得到最優(yōu)解C*={s3,s4,s5}.

        示例2 X={1,2,3,4},F(xiàn)={s1,s2,s3,s4},其中s1={1,2},s2={2,3},s3={3,4},s4={4,1}.

        圖6 二分圖Fig.6 Bipartite graph

        分析:

        由下界子算法求得b=2,當(dāng)執(zhí)行算法的第f步時(shí),由上界子算法求得u=2,由于u=b,因此,求得最優(yōu)解為C*={s1,s3}.

        示例3 X={a,b,c,d,e,f},F(xiàn)={s1,s2,s3,s4,s5},其中s1={a,b},s2={a,f},s3={d,e},s4={c,e},s5={b,c,d}.

        分析:

        step 1 先將該問題轉(zhuǎn)成如圖7所示的二分圖;

        step 2 按照規(guī)則1,并將s2加到最小子集C*中,得C*={s2},將結(jié)點(diǎn)s2、結(jié)點(diǎn)集N(s2)及其關(guān)聯(lián)邊從圖中刪除;

        step 3 按照規(guī)則2,將s1及其關(guān)聯(lián)邊刪除;

        step 4 再按照規(guī)則1,將s5加到最小子集C*中,得C*={s2,s5},將結(jié)點(diǎn)s5、結(jié)點(diǎn)集N(s5)及其關(guān)聯(lián)邊從圖中刪除;

        step 5 最后將s3加到最小子集C*中,得到最優(yōu)解C*={s2,s3,s5},或者把s4加到最小子集C*中,得到最優(yōu)解C*={s2,s4,s5}.

        圖7 二分圖Fig.7 Bipartite graph

        3 算法對(duì)比分析

        對(duì)于集合覆蓋問題,目前國(guó)內(nèi)外主要有兩種處理方法:一種是啟發(fā)式算法[2,3],啟發(fā)式算法的優(yōu)點(diǎn)是能夠快速得到可行解,其缺點(diǎn)是不能保證解是最優(yōu)解,也不能提供解的近似比;另外一種是采用精確算法或近似算法[1,4],比如分枝定界法、回溯法等,精確算法的優(yōu)點(diǎn)是能得到最優(yōu)解,但時(shí)間復(fù)雜度都是指數(shù)級(jí)別的,難以處理規(guī)模較大的問題,近似算法在近似程度上提供保障,但不能得到最優(yōu)解.

        本降階算法的優(yōu)點(diǎn)在于利用問題的性質(zhì)及上下界來加快問題的求解速度,使原問題變?yōu)橐?guī)模更小的同性質(zhì)的子問題,便于進(jìn)一步的處理;不足之處在于只能對(duì)部分實(shí)例問題求解得到最終解,對(duì)不能得到最終解的問題實(shí)例還必須與其它方法結(jié)合起來才能得到最終解,比如對(duì)于經(jīng)過降階算法處理后的子問題,若規(guī)模較少,可以用分枝定界法來得到最優(yōu)解,若規(guī)模仍然很大,則可以用啟發(fā)式算法來求解.

        4 結(jié)束語

        集合覆蓋問題是不具有多項(xiàng)式時(shí)間算法的NP難題,本文提供的降階算法能在一定程度上降低原問題的求解規(guī)模與難度,而且在某些情況下,能直接得出問題的最優(yōu)解.該方法不僅可以單獨(dú)使用,而且可以與其它方法結(jié)合起來使用,從而加快問題的求解速度.

        [1] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].3版.北京:電子工業(yè)出版社,2007.

        [2] 陳端兵,黃文奇.一種求解集合覆蓋問題的啟發(fā)式算法[J].計(jì)算機(jī)科學(xué),2007,34(4):133-136.

        [3] Chvatal V.A greedy heuristic for the set covering problem[J].Mathematics of Operations Research,1979,4(3):233-235.

        [4] Hassin R,Levin A.A better than greedy approximation algorithm for the minimum set cover problem[J].SIAM Journal on Computing,2005,35(1):189-200.

        猜你喜歡
        降階下界子集
        由一道有關(guān)集合的子集個(gè)數(shù)題引發(fā)的思考
        拓?fù)淇臻g中緊致子集的性質(zhì)研究
        單邊Lipschitz離散非線性系統(tǒng)的降階觀測(cè)器設(shè)計(jì)
        關(guān)于奇數(shù)階二元子集的分離序列
        Lower bound estimation of the maximum allowable initial error and its numerical calculation
        降階原理在光伏NPC型逆變微網(wǎng)中的應(yīng)用研究
        基于Krylov子空間法的柔性航天器降階研究
        基于CFD降階模型的陣風(fēng)減緩主動(dòng)控制研究
        矩陣Hadamard積的上下界序列
        最大度為10的邊染色臨界圖邊數(shù)的新下界
        国产精品人人爱一区二区白浆| 久久精品网站免费观看| 99久久精品免费看国产| 国内露脸少妇精品视频| 最近中文av字幕在线中文| 级毛片无码av| 国产精品自拍网站在线| 中文字幕日韩有码在线| 国产做国产爱免费视频| 久无码久无码av无码| 亚洲AV秘 无码一区二区三区| 亚洲国产av午夜福利精品一区| 亚洲丝袜美腿在线视频| 99久久免费只有精品国产| 国产高清乱理伦片| AⅤ无码精品视频| 熟女高潮av一区二区| 亚洲av天堂免费在线观看| 中文字幕日韩一区二区不卡| 久草热8精品视频在线观看| 亚洲av伊人久久综合性色| 精品人妻码一区二区三区红楼视频| 2018天天躁夜夜躁狠狠躁| 免费观看性欧美大片无片 | 亚洲熟妇在线视频观看| 亚洲综合免费在线视频| 国产饥渴的富婆一凶二区| 日韩精品视频一区二区三区| 天堂√中文在线bt| 亚洲AV秘 无套一区二区三区| 亚洲天堂男人的av天堂| 十八禁视频在线观看免费无码无遮挡骂过| 私人毛片免费高清影视院| 91网站在线看| 高清亚洲成av人片乱码色午夜| 91久久国产香蕉视频| 香港三级日本三级a视频| 色两性网欧美| 日韩一二三四区免费观看 | 无码一区二区三区| 国产成人啪精品视频免费软件|