集合覆蓋問題降階算法

寧愛兵， 劉艷芳， 王英磊

（上海理工大學(xué)管理學(xué)院，上海 200093）

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

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

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

1 問題及算法介紹

1.1 問題簡介

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

集合覆蓋問題的一個實(shí)例〈X，F(xiàn)〉由一個有限集X及X的一個子集族F組成.子集族F覆蓋了有限集X，也就是說X中每一元素至少屬于F中的一個子集，即對于F中的一個子集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的每個元素作為二分圖的一個頂點(diǎn)子集X，把F中的每個元素作為二分圖的另一個頂點(diǎn)子集F，F(xiàn)中的元素是集合.若F中的元素f1包含X中的元素x1，則在f1與x1之間連線，否則不連線.

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

1.3 數(shù)學(xué)符號

為了方便描述，除了問題簡介和問題轉(zhuǎn)換中定義的符號外，還定義如下符號：

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

m表示二分圖G中頂點(diǎn)集F中結(jié)點(diǎn)的個數(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＊中元素個數(shù)的下界，即｜C＊｜≥b；

u表示最小覆蓋子集C＊中元素個數(shù)的上界，即｜C＊｜≤u.

1.4 下界子算法

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

a.i＝1；

b.集合temp＿c＝Φ；

c.若i＞n或者temp＿c中元素的數(shù)量為m，則整個算法結(jié)束并得到下界b；

d.對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個度最大的結(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），修改對應(yīng)結(jié)點(diǎn)的d（vi），跳到第c步.

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

1.6 降階規(guī)則

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

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

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

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

在降階的中間過程中，可能會出現(xiàn)度為0的結(jié)點(diǎn)，也可能在F中存在1個能覆蓋X中所有結(jié)點(diǎn)的子集合f1，此時采用規(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中存在一個結(jié)點(diǎn)f1覆蓋X中的所有結(jié)點(diǎn)，則將f1加入到最小子集C＊中.

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

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

1.7 降階算法

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

a.下界b＝0，C＊＝Φ；

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

c.按照規(guī)則1，對于X中度為1的結(jié)點(diǎn)xi，把其關(guān)聯(lián)邊對應(yīng)的另一個結(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)邊從圖中刪除，并修改對應(yīng)點(diǎn)的度d（vi），修改變量n和m.這樣持續(xù)做下去，直到X中不存在度為1的結(jié)點(diǎn)為止；

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

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

f.采用規(guī)則3和規(guī)則4來降階，調(diào)用上界子算法求出上界u，若此時u＝b，則令C1為上界子算法中的temp＿c，此時C＊＝C＊∪C1為最優(yōu)解，整個算法結(jié)束；

g.j＝0；

h.若j＞m，則跳到第o步；

i.對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）中每一個結(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）從圖中刪除，同時執(zhí)行m＝m－1，n＝n－｜N（fj）｜，u＝u－1，并修改對應(yīng)點(diǎn)的度；

n.采用規(guī)則3和規(guī)則4來降階；j＝j(luò)＋1，跳到第h步；

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

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

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

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

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

2 示例分析

為了更清楚地了解算法的原理及應(yīng)用情況，下面給出3個示例來進(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，對于X中度為1的結(jié)點(diǎn)l，將其關(guān)聯(lián)邊對應(yīng)的另一個結(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)邊從圖中刪除，并修改對應(yīng)點(diǎn)的度d（vi），修改變量n＝8和m＝5，得到圖3所示的圖形；

圖3 二分圖Fig.3 Bipartite graph

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

Step 5 按照規(guī)則1，對于X中度為1的結(jié)點(diǎn)g，把其關(guān)聯(lián)邊對應(yīng)的另一個結(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)邊從圖中刪除，并修改對應(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，此時u＝b，得到最優(yōu)解C＊＝｛s3，s4，s5｝，整個算法結(jié)束.

分析方法二：

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

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

Step 7 執(zhí)行算法的第f步，求得上界u＝2；

Step 8 執(zhí)行算法的第i步，對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｝中每個結(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步時，由上界子算法求得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 算法對比分析

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

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

4 結(jié)束語

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

［1］ 王曉東.計算機(jī)算法設(shè)計與分析［M］.3版.北京：電子工業(yè)出版社，2007.

［2］ 陳端兵，黃文奇.一種求解集合覆蓋問題的啟發(fā)式算法［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.