加權互斥最大集合覆蓋問題的精確算法

周曉清，葉安勝，張志強

(1.電子科技大學 計算機科學與工程學院，四川 成都 611731；2.成都大學 信息科學與工程學院，四川 成都 610106)

0 引 言

1 問題及符號的定義

1.1 加權互斥最大集合覆蓋問題的定義

1.2 問題轉換

1.3 符號定義

為了描述方便，文中還定義如下符號：

1.4 遞歸算法時間復雜度的通用公式

假設基于分支搜索方法的遞歸算法下某個分支后，得到如下的一個遞推公式T(n)≤T(n-n1)+T(n-n2)+…+T(n-nr)， 即將原問題分解為r個大小的子問題，其中r≥2，n為原問題的規模(比如圖中的頂點數)，ni和n-ni分別為原問題分支后第i個子問題的減少量和第i個子問題規模。令T(n)=xn， 則上述遞推公式可以轉化為求解方程xn-xn-n1-xn-n2-…-xn-nr=0的最大實根。設c為該方程的最大實根，則在該分支下最壞的時間復雜度為O*(cn)， 稱c為該遞歸關系式的分支因子。由于分支搜索算法不止一個分支，那么就將算法所有分支中最差的運行時間作為整個算法運行時間上界。

2 算法的設計及相關的性質定理

2.1 算法初步思想

2.2 性質和定理

以下將證明算法設計中用到的一些性質和定理。

證明：假設OPT為實例I中不包含頂點v的最優解，那么存在另外一個可行解OPT′=OPT∪v， 使得 |OPT′∩X|>|OPT∩X| 成立，這與OPT為最優解相矛盾，所以可以將度為0的頂點直接加入解中。

證明：由于交集圖G的最大度Δ(G)≤1， 所以交集圖G中頂點只存在以下兩種情況，要么是度為0的獨立點，要么是兩個頂點相連的線段。

對于第一種情況，根據性質1可知，可直接將度為0的頂點加入解中。對于第二鐘情況，首先判斷兩個頂點與X相交的情況，將與X相交元素更多的那個頂點加入解，如果兩個頂點同X相交元素一樣多，那么將權重較小的那個頂點加入解。如此反復操作，即可在多項式時間內解決該問題。

證明：由于交集圖G中頂點的最大度Δ(G)≤2， 那么交集圖G僅可能是由一條簡單的路或者環構成，下面分這兩種情況來討論解決該問題需要的時間。

情況1：假設交集圖G是一條簡單路。那么首先找到這條路中間的頂點v， 然后從頂點v開始分支，要么將v加入解中(頂點v及其v鄰居共3個頂點將從實例I中刪除)，要么v不在解中(頂點v從實例I中刪除)，所以該分支的遞歸關系式為T(m)≤T(m-3)+T(m-1)。 經過分支后，交集圖G將會分成兩個差不多大小的連通分量，有以下遞歸關系式

解遞歸關系式得T(m)≤4logm=m2， 所以可在多項式時間內解決。

情況2：假設交集圖G是一個環，那么從環中任意選一個頂點v進行分支。同情況1的分析類似，要么將頂點v加入解中，要么頂點v不在解中，因此也有如下遞歸關系式T(m)≤T(m-3)+T(m-1)。 在該操作后，交集圖G成為一條簡單路徑，所以同情況1 的分析可知，有T(m)≤(m-3)2+(m-1)2<2m2， 所以可在多項式時間內解決。

如果交集圖G是由多個簡單路和環構成，可以獨立求解各個連通分量，然后將所有連通分量求出的解合并起來就為該原問題的解。由于每個連通分量導出的子實例可以在多項式時間內求解，那么原問題可以在多項式時間內解決。

2.3 解決加權互斥最大集合覆蓋問題的精確算法

下面是一個求解加權互斥最大集合覆蓋問題的精確算法，其主要步驟參見算法1。

輸入：加權互斥最大集合覆蓋問題的一個實例。

輸出：一個最小權重的互斥最大集合覆蓋集。

(4)否則如果Δ(G)≤2， 返回多項式時間內求出的較優解。

3 算法運行時間的分析

3.1 傳統方法分析算法時間復雜度

其中，m為交集圖G中的頂點數。設T(μ) 為搜索樹產生的葉子結點數，那么算法中第(3)步的分支操作將產生如下的遞歸關系式子

T(μ)≤T(μ-(1+d(v)))+T(μ-1)

3.2 測量治之方法分析算法時間復雜度

不同于傳統分析方法中將圖中的頂點數作為問題的度量，測量治之方法會選擇一個更加復雜的度量，這可能會在分析過程中獲得一些傳統方法所不能得到的算法運行細節，從而可以對給定算法進行更緊致的分析。例如將圖中的頂點區分對待，根據圖中頂點度的不同對每個頂點賦予不同的權值。可以按如下方式設置賦值方案：

(1)度為0的頂點，權值設為0；

(2)度為1的頂點，權值設為α；

(3)度為2的頂點，權值設為β；

(4)度大于等于3的頂點，權值設為1；

(1)

其中，α和β是滿足0<α<β<1的實數，ni表示圖中度為i的頂點總數，n≥i表示圖中度大于等于i的頂點總數，α和β的值在文章的后面給出。

T(μ)≤T(μ-(1+α×r1+β×r2+r≥3))+
T(μ-(1+α×r1+(β-α)×r2+(1-β)×r3))

(2)

下面根據式(1)中設置的度量，分析該遞歸關系式的時間復雜度。

情況1.1：當d(v)≤2時，根據定理2可知其時間復雜性為多項時間。

情況1.2：當d(v)=3時，此時算法的時間復雜度根據式(2)分情況計算在表1中。表1計算了交集圖G中度為3時的所有可能性，由表1可知在情況1.2下最壞的時間復雜度為O*(1.3172μ)， 又在初始圖上μ

表1 情況1.2下遞歸關系式和時間復雜度

情況1.3：當d(v)=4時，此時算法的時間復雜度根據式(2)分情況計算在表2中，表2計算了交集圖G中度為4時的所有可能性，由表2可知在情況1.3下最壞的時間復雜度為O*(1.3247μ)， 同樣在初始圖上μ

表2 情況1.3下遞歸關系式和時間復雜度

情況1.4：當d(v)≥5時，此時采用頂點總數為問題規模的傳統分析方法有如下遞歸關系式T(μ)≤T(μ-6)+T(μ-1)， 用1.4小節的方法解得算法的時間復雜度為O*(1.2852m)。

綜上4種情況，得到加權互斥最大集合覆蓋問題可以在O*(1.3247m) 時間內解決，該結果改進了傳統方法分析得到的運行時間界O*(1.3803m)。 其中α=0.5687和β=0.8499是將表1和表2中所有遞歸關系式作為約束條件組成一個擬凸規劃的約束條件，然后對這個擬凸規劃求解得到。

3.3 基于測量治之方法改變度量設置進一步改進算法時間復雜度

(3)

其中，α、β和γ滿足0<α<β<γ<1的實數，α、β和γ的值在本文的后面給出。

T(μ)≤T(μ-(1+α×r1+β×r2+γ×r3+r≥4))+
T(μ-(1+α×r1+(β-α)×r2+
(γ-β)×r3+(1-γ)×r4))

(4)

下面根據式(3)中設置的度量，分情況來分析該遞歸關系式的時間復雜度。

情況2.1：當d(v)≤2時，根據定理2可知其時間復雜性為多項時間。

情況2.2：當d(v)=3時，此時算法的時間復雜度根據式(4)分情況計算在表3中。表3計算了交集圖G中度為3時的所有可能性，由表3可知在情況2.2下最壞的時間復雜度為O*(1.3131μ)， 又在初始圖上μ

表3 情況2.2下遞歸關系式和時間復雜度

情況2.3：當d(v)=4時，此時算法的時間復雜度根據式(4)分情況計算在表4中，表4計算了交集圖G中度為4時的所有可能性，由表4可知在情況2.3下最壞的時間復雜度為O*(1.3132μ)， 同樣在初始圖上μ

表4 情況2.3下遞歸關系式和時間復雜度

表4(續)

情況2.4：當d(v)≥5時，此時采用頂點總數為問題規模的傳統分析方法有如下遞歸關系式T(μ)≤T(μ-6)+T(μ-1)， 用1.4小節的方法解得算法的時間復雜度為O*(1.2852m)。

綜上4種情況，得到加權互斥最大集合覆蓋問題可以在O*(1.3132m) 時間內解決，該結果改進了3.2小節分析的運行時間界O*(1.3247m)。 同樣按3.2小節所述的方法求解得到α=0.5148、β=0.7991和γ=0.9785。

4 結束語

本文首先將加權互斥最大集合覆蓋問題轉化成圖上的問題進行處理，然后證明了算法中使用到性質和定理，在此基礎上設計了一個分支搜索算法，最后分別采用了兩種不同的分析方法分析算法的時間復雜度。第一種方法采用傳統方法分析算法時間復雜度，是將圖中頂點數作為問題實例的度量，得到算法的時間復雜度為O*(1.3803m)。 第二種方法采用測量治之方法，根據頂點對問題整體難易程度的貢獻，對度不同的頂點設置不同的權重，得到了算法時間復雜度為O*(1.3247m)， 在進一步設置更加細致的度量后，得到算法時間復雜度為O*(1.3132m)， 改進了該問題原有的最佳運行時間界O*(1.325m)。