集合覆蓋問題降階算法

寧愛兵， 劉艷芳， 王英磊

（上海理工大學管理學院，上海 200093）

集合覆蓋問題（set covering problem，SCP）是組合優化中一個典型NP（non－deterministic polynomial time，非確定多項式時間算法）難解問題，是計算機和運籌學中的一個經典問題，在人員調動、網絡安全、資源分配、電路設計、運輸車輛路徑安排等領域有著廣泛的應用［1－4］.

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

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

1 問題及算法介紹

1.1 問題簡介

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

集合覆蓋問題的一個實例〈X，F〉由一個有限集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 問題轉換

在算法處理之前，將該問題轉換成二分圖來進行處理，轉換方法如下：

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

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

1.3 數學符號

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

n表示二分圖G中頂點集X中結點的個數；

m表示二分圖G中頂點集F中結點的個數；

d（vi）表示結點vi的度，其值為與vi關聯邊的條數；

N（vi）表示二分圖中頂點vi的鄰點集，N（vi）＝｛vj｜（vi，vj）∈E｝；

Φ表示空集；

b表示最小覆蓋子集C＊中元素個數的下界，即｜C＊｜≥b；

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

1.4 下界子算法

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

a.i＝1；

b.集合temp＿c＝Φ；

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

d.對X中的元素xi，若N（xi）∩temp＿c＝Φ，則i＝i＋1，b＝b＋1，temp＿c＝N（xi）∪temp＿c并跳至第c步，否則執行i＝i＋1并跳至第c步.

算法中的N（xi）∩temp＿c＝Φ說明目前還沒有集合覆蓋xi.

1.5 上界子算法

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

a.令G2為待處理的二分圖，X2＝X，F2＝F；

b.u＝0，集合temp＿c＝Φ；

c.若X2為空集，則算法結束，否則跳至第d步；

d.在F2中找出1個度最大的結點f1，其中f1∈F2；

e.u＝u＋1，temp＿c＝temp＿c∪｛f1｝，在二分圖G2中刪除結點f1及其關聯邊，F2＝F2－｛f1｝，刪除集合N（f1）中的結點及其關聯邊，X2＝X2－N（f1），修改對應結點的d（vi），跳到第c步.

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

1.6 降階規則

規則1 對頂點集X中度為1的結點xi，其關聯邊對應的另一個結點fj一定在最小子集C＊中.

證明 因為度為1的結點xi必須被某個集合覆蓋，而xi僅僅只屬于一個集合fj，故要覆蓋xi，則fj一定在最小子集C＊中.

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

證明 因為N（f1）?N（f2），所以f1所起到的覆蓋作用完全可以由f2來代替.代替后的覆蓋功能只會更強，而不會更弱，而目標函數最小子集C＊中的數量不變.因此可以把頂點f1及其關聯邊從圖中刪除而不會影響最小子集C＊求解.

在降階的中間過程中，可能會出現度為0的結點，也可能在F中存在1個能覆蓋X中所有結點的子集合f1，此時采用規則3和規則4來降階.

規則3 在降階的任何過程中，可以將頂點集F中度為0的結點f1直接從圖中刪除.

證明 由于頂點集F中度為0的結點f1不能覆蓋任何結點，因此可以直接刪除.

規則4 在降階的任何過程中，若頂點集F中存在一個結點f1覆蓋X中的所有結點，則將f1加入到最小子集C＊中.

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

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

1.7 降階算法

對于已經轉成二分圖的問題，采用如下算法進行降階：

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

b.調用下界子算法求出下界b；

c.按照規則1，對于X中度為1的結點xi，把其關聯邊對應的另一個結點fj加到最小子集C＊中，b＝b－1，并把結點xi及其關聯邊從圖中刪除.將結點fj、結點集合N（fj）及其關聯邊從圖中刪除，并修改對應點的度d（vi），修改變量n和m.這樣持續做下去，直到X中不存在度為1的結點為止；

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

e.若d中刪除過結點，則跳到第c步，否則執行下一步；

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

g.j＝0；

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

i.對F中的元素fj，令N2（fj）為N（fj）中度為2的結點集合，若N2（fj）中結點數量大于等于u，則執行下一步，否則跳到第n步；

j.集合temp＿c＝Φ；

k.把N2（fj）中每一個結點vi的鄰點集N（vi）加到集合temp＿c中；

l.temp＿c＝temp＿c－fj（這里操作的含義是假設fj不在最小子集C＊中）；

m.若temp＿c的數量大于u，則把結點fj加到最小子集C＊中，把結點fj和結點集合N（fj）從圖中刪除，同時執行m＝m－1，n＝n－｜N（fj）｜，u＝u－1，并修改對應點的度；

n.采用規則3和規則4來降階；j＝j＋1，跳到第h步；

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

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

1.8 算法的時間復雜度分析

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

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

2 示例分析

為了更清楚地了解算法的原理及應用情況，下面給出3個示例來進行分析.

示例1 求圖1（見下頁）中圖G的最小集合覆蓋，其中，X＝｛a，b，c，d，e，f，g，h，i，j，k，l｝，F＝｛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｝，該示例取自文獻［1］，文獻［1］提供的近似算法.

分析方法一：

Step 1 先把圖1轉成如圖2（見下頁）所示的二分圖；

圖1 示例1Fig.1 Instance 1

圖2 二分圖Fig.2 Bipartite graph

Step 2 調用下界子算法求出下界b＝3；

Step 3 按照規則1，對于X中度為1的結點l，將其關聯邊對應的另一個結點s5加到最小子集C＊中，得C＊＝｛s5｝，b＝b－1＝2，并將結點l及其關聯邊從圖中刪除，把結點s5、結點集N（s5）及其關聯邊從圖中刪除，并修改對應點的度d（vi），修改變量n＝8和m＝5，得到圖3所示的圖形；

圖3 二分圖Fig.3 Bipartite graph

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

Step 5 按照規則1，對于X中度為1的結點g，把其關聯邊對應的另一個結點s4加到最小子集C＊中，得C＊＝｛s4，s5｝，b＝b－1＝1，并將結點g及其關聯邊從圖中刪除，把結點s4、結點N（s4）及其關聯邊從圖中刪除，并修改對應點的度d（vi），修改變量n＝3和m＝3，得到圖5所示的圖形；

圖4 二分圖Fig.4 Bipartite graph

圖5 二分圖Fig.5 Bipartite graph

Step 6 執行算法的第f步，求得上界u＝1，此時u＝b，得到最優解C＊＝｛s3，s4，s5｝，整個算法結束.

分析方法二：

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

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

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

Step 8 執行算法的第i步，對F中的元素s3，N2（s3）＝｛a，b，c，d｝為N（s3）中度為2的結點集合，由于N2（s3）中結點數量大于等于u，則跳到算法的第j步；

Step 9 執行算法的第j步，集合temp＿c＝Φ；

Step 10 執行算法的第k步，將N2（s3）＝｛a，b，c，d｝中每個結點vi的鄰點集N（vi）加到集合temp＿c中，得temp＿c＝｛s1，s3，s4，s6｝；

Step 11 執行算法的第l步，得temp＿c＝temp＿c－fi＝｛s1，s4，s6｝

Step 12 執行算法的第m步，C＊＝｛s3，s5｝，將結點s3、結點集N（s3）從圖中刪除，m＝m－1＝4，n＝4，u＝u－1＝1，得到圖6；

Step 13 執行算法的第n步，采用規則4來降階得到最優解C＊＝｛s3，s4，s5｝.

示例2 X＝｛1，2，3，4｝，F＝｛s1，s2，s3，s4｝，其中s1＝｛1，2｝，s2＝｛2，3｝，s3＝｛3，4｝，s4＝｛4，1｝.

圖6 二分圖Fig.6 Bipartite graph

分析：

由下界子算法求得b＝2，當執行算法的第f步時，由上界子算法求得u＝2，由于u＝b，因此，求得最優解為C＊＝｛s1，s3｝.

示例3 X＝｛a，b，c，d，e，f｝，F＝｛s1，s2，s3，s4，s5｝，其中s1＝｛a，b｝，s2＝｛a，f｝，s3＝｛d，e｝，s4＝｛c，e｝，s5＝｛b，c，d｝.

分析：

step 1 先將該問題轉成如圖7所示的二分圖；

step 2 按照規則1，并將s2加到最小子集C＊中，得C＊＝｛s2｝，將結點s2、結點集N（s2）及其關聯邊從圖中刪除；

step 3 按照規則2，將s1及其關聯邊刪除；

step 4 再按照規則1，將s5加到最小子集C＊中，得C＊＝｛s2，s5｝，將結點s5、結點集N（s5）及其關聯邊從圖中刪除；

step 5 最后將s3加到最小子集C＊中，得到最優解C＊＝｛s2，s3，s5｝，或者把s4加到最小子集C＊中，得到最優解C＊＝｛s2，s4，s5｝.

圖7 二分圖Fig.7 Bipartite graph

3 算法對比分析

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

本降階算法的優點在于利用問題的性質及上下界來加快問題的求解速度，使原問題變為規模更小的同性質的子問題，便于進一步的處理；不足之處在于只能對部分實例問題求解得到最終解，對不能得到最終解的問題實例還必須與其它方法結合起來才能得到最終解，比如對于經過降階算法處理后的子問題，若規模較少，可以用分枝定界法來得到最優解，若規模仍然很大，則可以用啟發式算法來求解.

4 結束語

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

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

［2］ 陳端兵，黃文奇.一種求解集合覆蓋問題的啟發式算法［J］.計算機科學，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.