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

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

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

0 引 言

1 問題及符號(hào)的定義

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

1.2 問題轉(zhuǎn)換

1.3 符號(hào)定義

為了描述方便，文中還定義如下符號(hào)：

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

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

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

2.1 算法初步思想

2.2 性質(zhì)和定理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

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

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

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

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

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

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

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

(3)

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

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

(4)

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

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

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

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

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

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

表4(續(xù))

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

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

4 結(jié)束語

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