周曉清，葉安勝，張志強(qiáng)

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

0 引 言

1 問題及符號的定義

1.1 加權(quán)互斥最大集合覆蓋問題的定義

1.2 問題轉(zhuǎn)換

1.3 符號定義

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

1.4 遞歸算法時間復(fù)雜度的通用公式

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

2 算法的設(shè)計及相關(guān)的性質(zhì)定理

2.1 算法初步思想

2.2 性質(zhì)和定理

以下將證明算法設(shè)計中用到的一些性質(zhì)和定理。

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

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

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

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

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

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

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

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

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

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

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

輸出：一個最小權(quán)重的互斥最大集合覆蓋集。

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

3 算法運(yùn)行時間的分析

3.1 傳統(tǒng)方法分析算法時間復(fù)雜度

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

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

3.2 測量治之方法分析算法時間復(fù)雜度

不同于傳統(tǒng)分析方法中將圖中的頂點數(shù)作為問題的度量，測量治之方法會選擇一個更加復(fù)雜的度量，這可能會在分析過程中獲得一些傳統(tǒng)方法所不能得到的算法運(yùn)行細(xì)節(jié)，從而可以對給定算法進(jìn)行更緊致的分析。例如將圖中的頂點區(qū)分對待，根據(jù)圖中頂點度的不同對每個頂點賦予不同的權(quán)值?？梢园慈缦路绞皆O(shè)置賦值方案：

(1)度為0的頂點，權(quán)值設(shè)為0；

(2)度為1的頂點，權(quán)值設(shè)為α；

(3)度為2的頂點，權(quán)值設(shè)為β；

(4)度大于等于3的頂點，權(quán)值設(shè)為1；

(1)

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

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

(2)

下面根據(jù)式(1)中設(shè)置的度量，分析該遞歸關(guān)系式的時間復(fù)雜度。

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

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

表1 情況1.2下遞歸關(guān)系式和時間復(fù)雜度

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

表2 情況1.3下遞歸關(guān)系式和時間復(fù)雜度

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

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

3.3 基于測量治之方法改變度量設(shè)置進(jìn)一步改進(jìn)算法時間復(fù)雜度

(3)

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

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

(4)

下面根據(jù)式(3)中設(shè)置的度量，分情況來分析該遞歸關(guān)系式的時間復(fù)雜度。

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

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

表3 情況2.2下遞歸關(guān)系式和時間復(fù)雜度

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

表4 情況2.3下遞歸關(guān)系式和時間復(fù)雜度

表4(續(xù))

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

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

4 結(jié)束語

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