精確覆蓋問題的加權(quán)分治算法

胡 沁， 寧愛兵， 茍海雯， 張惠珍

(上海理工大學(xué) 管理學(xué)院,上海 200093)

0 引言

精確覆蓋(exact cover, EC)及其各種變形問題在運(yùn)籌學(xué)、管理學(xué)、組合數(shù)學(xué)和計(jì)算機(jī)科學(xué)等領(lǐng)域被廣泛研究，例如針對陣列雷達(dá)子陣劃分問題[1]，該問題可做如下簡單概述：陣列雷達(dá)可分為許多子陣，然而囿于器件水平、系統(tǒng)成本及工程實(shí)現(xiàn)難度等因素的限制，每一子陣對區(qū)域的覆蓋范圍不同，其范圍類似于若干個多聯(lián)六邊形組成的非規(guī)則形狀。為了保證預(yù)警探測、空間監(jiān)視等軍事任務(wù)的安全性，在陣列雷達(dá)設(shè)計(jì)時，不僅需要保證對陣面全覆蓋而且需要降低工程實(shí)現(xiàn)的難度，如何做到只用特定非規(guī)則形狀的子陣對整個陣面進(jìn)行精確覆蓋是達(dá)到這一目標(biāo)的核心問題。除此之外精確覆蓋在信息科學(xué)[2]、自動化系統(tǒng)設(shè)計(jì)[3]、通信工程[4]及密鑰管理[5]等諸多領(lǐng)域亦具有非常廣泛的應(yīng)用，因此精確覆蓋問題具有極其重要的研究價值和意義，也是組合優(yōu)化中經(jīng)典的NP-Hard問題，除非P=NP，否則不存在多項(xiàng)式時間算法。

目前求解精確覆蓋問題的算法主要分為精確算法和啟發(fā)式算法。Donald Knuth在2000年首次提出了解決精確覆蓋問題的精確算法——X算法[6]，但隨著問題的規(guī)模和元素總個數(shù)的增加，求解問題的時間越來越長，隨后有許多學(xué)者開始嘗試改良X算法以加快求解速度[7]。近年來，大量學(xué)者開始嘗試運(yùn)用啟發(fā)式算法求解精確覆蓋問題，并取得了令人滿意的結(jié)果，如量子算法[8]、絕熱量子算法[9]、DNA計(jì)算機(jī)算法[10]、基于光學(xué)原理的算法[11]等。啟發(fā)式算法的優(yōu)點(diǎn)在于能夠快速得到問題的可行解，但無法確保所得到的解是問題最優(yōu)解。

分支降階技術(shù)由Davis和Putnam提出，是解決NP難題最常用的方法，其核心思想是先通過降階規(guī)則對問題規(guī)模進(jìn)行約減，再將簡化后的問題通過分支規(guī)則分解成若干小規(guī)模的子問題進(jìn)行求解。加權(quán)分治技術(shù)由Fomin、Grandoni和Kratsch提出[12,13]，目前基于加權(quán)分治技術(shù)的精確算法的設(shè)計(jì)和分析被廣泛應(yīng)用于求解NP-Hard問題中[14～17]，以期獲得最優(yōu)解的同時，降低算法的時間復(fù)雜度，其核心思想是根據(jù)問題中某個對象的重要程度來設(shè)置不同數(shù)值的權(quán)值，比如圖論中的某些問題可以根據(jù)圖中結(jié)點(diǎn)的度來設(shè)置每個結(jié)點(diǎn)的權(quán)值，結(jié)點(diǎn)的度不同，那么結(jié)點(diǎn)權(quán)值也可能不同，最后再以圖中結(jié)點(diǎn)的權(quán)值之和作為問題的規(guī)模，而不是像傳統(tǒng)方法以結(jié)點(diǎn)的個數(shù)作為問題的規(guī)模。以權(quán)值之和作為問題的規(guī)模能更加精確的描述原問題以及分支子問題規(guī)模的大小，達(dá)到降低精確算法時間復(fù)雜度的目的。

本文首先給出了EC問題的定義，問題的數(shù)學(xué)性質(zhì)及其證明；接著根據(jù)定義和數(shù)學(xué)性質(zhì)設(shè)計(jì)出基于分支降階的回溯算法，并利用傳統(tǒng)分析方法對算法進(jìn)行分析得出時間復(fù)雜度為O(1.4656k)；然后采用加權(quán)分治技術(shù)根據(jù)EC問題的不同特征設(shè)置相應(yīng)的權(quán)值，以權(quán)值之和作為問題的規(guī)模對算法進(jìn)行時間復(fù)雜度分析，把該算法的時間復(fù)雜度降為O(1.3842k)；最后對算法進(jìn)行對比分析并對全文內(nèi)容加以總結(jié)。

1 問題介紹及性質(zhì)

1.1 精確覆蓋問題簡介

F為集合X的若干個子集構(gòu)成的集合，若存在F的一個子集F*，滿足X中的元素有且僅有一次包含在F*的一個元素中，那么稱F*為X的一個精確覆蓋。上述定義中，F(xiàn)*中任意兩個元素交集為空且F*中所有元素并集為X。精確覆蓋問題是找出這樣的一種覆蓋F*，或證明其不存在。

如果F中存在集合為空集，那么該集合是否存在于精確覆蓋中沒有任何區(qū)別，因此通常假定：F*中的任一集合都至少包含一個元素，也就是說規(guī)定F中的空元素都不在精確覆蓋集合F*中。

1.2 問題轉(zhuǎn)換

在算法處理之前，本文把精確覆蓋問題轉(zhuǎn)換成二分圖來進(jìn)行處理，轉(zhuǎn)換方法如下：

將精確覆蓋問題中X的每個元素作為二分圖的一個元素子集X，把F中的每個元素作為二分圖的一個集合子集F，F(xiàn)中的元素是集合。若F中的元素fi包含X中的元素xi，則在fi與xi之間連線，否則不連線。

這樣處理后，得到一個圖G=(V,E)，其中V=X∪F，E={(x,f)|x∈X,f∈F且x∈f}。很顯然，圖G是二分圖。而原問題的求解變?yōu)樵诩献蛹疐中找出若干子集的集合F*，使得元素子集X中的每一個元素與F*中的元素有且僅有一條邊相連。

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

為了方便描述，采用如下數(shù)學(xué)符號表示：

N(v)：結(jié)點(diǎn)v的開鄰集，即與結(jié)點(diǎn)v之間存在一條邊的點(diǎn)的集合；

N[v]：結(jié)點(diǎn)v的閉鄰集，即N[v]=N(v)∪{v}；

d(v)：結(jié)點(diǎn)v的度，即與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的數(shù)目；

m：表示二分圖元素類X中的結(jié)點(diǎn)個數(shù)；

n：表示二分圖集合類F中的結(jié)點(diǎn)個數(shù)；

X：X={xi|i=1,2,…,m}，X為問題介紹中的集合X，X中共有m個元素；

F：F={fj|j=1,2,…,n}，F(xiàn)為問題介紹中的集合F，F(xiàn)中共有n個元素；

F0：F0為F的子集且F0中任一元素在精確覆蓋F*中則不能取得可行解，也就是說F中不能出現(xiàn)在精確覆蓋F*中的元素就放入到F0中；

F1：F1為F的子集且F1中任一元素不在精確覆蓋F*中則不能取得可行解，也就是說F中一定出現(xiàn)在精確覆蓋F*中的元素就放入到F1中；

FF0：對于集合F中的結(jié)點(diǎn)fi，在回溯算法分情況時假設(shè)其不在精確覆蓋F*中，則將其加入集合FF0；

FF1：對于集合F中的結(jié)點(diǎn)fi，在回溯算法分情況時假設(shè)其在精確覆蓋F*中，則將其加入集合FF1；

g(fi)：表示結(jié)點(diǎn)fi與Ffi中元素交集不為空的元素個數(shù)，也就是說Ffi中有g(shù)(fi)個元素集合與fi的交集不為空；

H(fi)：表示集合Ffi中與fi存在交集的結(jié)點(diǎn)集合，也就是說H(fi)是Ffi的最大子集且H(fi)中的每個元素與fi的交集都不為空。

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

設(shè)基于分支降階的遞歸算法得到如下的遞推公式：T(n)=T(n-t1)+T(n-t2)+…+T(n-tr)，其中n為原問題的規(guī)模；(n-t1),(n-t2),…,(n-tr)分別為第1,2, …,r個子問題的規(guī)模。

令T(n)=xn，則上述遞推式可以轉(zhuǎn)化為求方程xn=xn-t1+xn-t2+…+xn-tr的唯一或者最大解。設(shè)方程唯一或者最大解為α，則該算法在最壞情況下的時間復(fù)雜度為O(αn)。該方法的詳細(xì)信息參見文獻(xiàn)[12]。

1.5 數(shù)學(xué)性質(zhì)

性質(zhì)1在集合子集F中，若存在一結(jié)點(diǎn)fi且d(fi)=0，則結(jié)點(diǎn)fi必定不在精確覆蓋集合中。

證明由d(fi)=0可知，結(jié)點(diǎn)fi為空集，根據(jù)前面精確覆蓋問題的規(guī)定，結(jié)點(diǎn)fi必定不在精確覆蓋集合F*中。

性質(zhì)2在元素子集X中，對于X中的任一結(jié)點(diǎn)xi，若d(xi)=0，則問題無解，即不存在可行解。

證明若d(xi)=0，則說明xi無法被集合子集F中的任何元素覆蓋，問題顯然無解。

性質(zhì)3在集合子集F中，對于任意兩個結(jié)點(diǎn)f1和f2，若N(f1)=N(f2),則可以將f1和f2中的任一結(jié)點(diǎn)及其關(guān)聯(lián)邊從圖中刪除。

證明由于結(jié)點(diǎn)f1和f2在二分圖中起到的作用完全相同，因此根據(jù)精確覆蓋問題的性質(zhì)，兩者取其一即可滿足。

性質(zhì)4在集合子集F中，若任意結(jié)點(diǎn)fi都滿足d(fi)≤1，則該問題可以在多項(xiàng)式時間內(nèi)解決。

證明根據(jù)性質(zhì)1可以去掉集合F中所有度為0的結(jié)點(diǎn)，由于集合F中所有結(jié)點(diǎn)的度都小于等于1，所以之后只剩下度為1的結(jié)點(diǎn)，再利用性質(zhì)3可以去掉覆蓋元素相同的結(jié)點(diǎn)，則二分圖中剩下的fi和xi之間必定是一一對應(yīng)的關(guān)系，顯然問題可以在多項(xiàng)式時間內(nèi)解決。

性質(zhì)5若集合子集F中存在一結(jié)點(diǎn)fi,g(fi)=0且結(jié)點(diǎn)fi不為空集，那么結(jié)點(diǎn)fi必定在精確覆蓋集合中。

證明根據(jù)性質(zhì)1，可以把d(fi)=0的結(jié)點(diǎn)從集合F中移除，之后集合F中的任一結(jié)點(diǎn)fi，都有d(fi)≥1，g(fi)=0說明結(jié)點(diǎn)fi與集合F中的其它任何結(jié)點(diǎn)都不存在交集，那么N(fi)中的元素只能由結(jié)點(diǎn)fi來覆蓋，因此結(jié)點(diǎn)fi一定在精確覆蓋集合中，否則N(fi)中的元素?zé)o法被覆蓋。

性質(zhì)6在元素子集X中，若存在一結(jié)點(diǎn)xi且d(xi)=1，那么覆蓋xi的結(jié)點(diǎn)fi一定在精確覆蓋集合中。

證明根據(jù)精確覆蓋問題的定義，顯然成立，否則xi無法被覆蓋。

性質(zhì)7在二分圖中，若結(jié)點(diǎn)fm是集合子集F中g(shù)(fi)值最大的結(jié)點(diǎn)，如果此時g(fm)≤1，則問題可在多項(xiàng)式時間內(nèi)求解。

證明由性質(zhì)5可以去掉所有g(shù)(fi)=0的結(jié)點(diǎn)，因?yàn)間(fm)≤1，那么之后集合F中任一結(jié)點(diǎn)fi的g(fi)值都等于1，不妨設(shè)與結(jié)點(diǎn)fm存在交集的結(jié)點(diǎn)為ft，再根據(jù)性質(zhì)6可以去掉必定在精確覆蓋集合中的結(jié)點(diǎn)，此時圖中僅剩下一種情況即N(fm)=N(ft)，根據(jù)性質(zhì)3可以去掉兩者之中任意一個結(jié)點(diǎn)。集合F中其它結(jié)點(diǎn)也可以這樣處理，因此此時問題可以在多項(xiàng)式時間內(nèi)解決。

2 算法設(shè)計(jì)及復(fù)雜性分析

2.1 精確覆蓋問題的求解算法

在前面數(shù)學(xué)性質(zhì)的基礎(chǔ)上，設(shè)計(jì)如下求解算法：

Step1初始化：輸入圖G，集合X，集合F，此時F0={}，F(xiàn)1={}，F(xiàn)F0={}，F(xiàn)F1={};

Step2根據(jù)性質(zhì)1，若在集合子集F中存在度為0的結(jié)點(diǎn)fi，那么該結(jié)點(diǎn)一定不在精確覆蓋中，F(xiàn)0=F0∪{fi}，F(xiàn)=F{fi}，同時從圖中刪除結(jié)點(diǎn)fi；

Step3根據(jù)性質(zhì)3，若在集合子集F中存在N(f1)=N(f2)的兩個結(jié)點(diǎn)f1和f2，則可以將兩者之中任一結(jié)點(diǎn)加入集合F0，同時將該結(jié)點(diǎn)從集合F中移除，并將該結(jié)點(diǎn)及其相關(guān)聯(lián)的邊從圖中刪除；

Step4根據(jù)性質(zhì)5，若圖G中存在一結(jié)點(diǎn)fi且g(fi)= 0，則F1=F1∪{fi}，F(xiàn)=F{fi}，同時從圖中刪除結(jié)點(diǎn)集N[fi]及其相關(guān)聯(lián)的邊；

Step5根據(jù)性質(zhì)6，如果圖G中存在結(jié)點(diǎn)xi∈X且d(xi)=1，N(xi)=fi，則F1=F1∪{fi}，F(xiàn)=F{fi}，同時從圖中刪除結(jié)點(diǎn)集N[fi]及其相關(guān)聯(lián)的邊，F(xiàn)0=F0∪H(fi)，F(xiàn)=FH(fi)，并將H(fi)中的結(jié)點(diǎn)及其相關(guān)聯(lián)的邊從圖中刪除；

Step6利用前面的數(shù)學(xué)性質(zhì)1到性質(zhì)6對問題進(jìn)行降階處理之后分兩種情況：(1)由性質(zhì)7得到問題的最優(yōu)解，則算法結(jié)束；(2)還無法得到問題的最優(yōu)解，則跳到Step 7；

Step7k=|F|；調(diào)用回溯子算法Backtrack(1)。

回溯子算法Backtrack(i)描述如下：

Step1若i>k，說明搜索到達(dá)葉子結(jié)點(diǎn)，此時對應(yīng)一個可行解，即得到一個精確覆蓋集合F1∪FF1，檢查F1∪FF1是否覆蓋元素子集X中的所有元素，如果滿足條件，回溯子算法Backtrack(i)結(jié)束；若i≤k，則跳到Step 2；

Step2利用二叉樹來搜索最優(yōu)解，其過程為：從集合F中取出g(fi)值最大的結(jié)點(diǎn)fm，對結(jié)點(diǎn)fm分下面步驟中的(1)和(3)兩種情況處理，具體步驟如下：

(1)情況1：假設(shè)結(jié)點(diǎn)fm在精確覆蓋集合中，令局部集合變量temp0={}，temp1={}，此時檢查(F1∪FF1∪F)H(fm)是否覆蓋元素子集X中的所有元素，若不能覆蓋，說明這種情況下沒有可行解，則剪枝，不進(jìn)入左子樹，并跳到下面的(3)去嘗試進(jìn)入右子樹；若能覆蓋，說明這種情況下有可行解，此時temp1=temp1∪{fm}，F(xiàn)F1=FF1∪{fm}，F(xiàn)=F{fm}，在二分圖中刪除結(jié)點(diǎn)集N[fm]以及其相關(guān)聯(lián)的邊，temp0=temp0∪H(fm)，F(xiàn)F0=FF0∪H(fm)，F(xiàn)=FH(fm)，并將H(fm)中的結(jié)點(diǎn)及其相關(guān)聯(lián)的邊從圖中刪除；利用性質(zhì)1到性質(zhì)6對于集合F中的結(jié)點(diǎn)進(jìn)行降階處理，若結(jié)點(diǎn)fi必定在精確覆蓋集合中，那么temp1=temp1∪{fi}，F(xiàn)F1=FF1∪{fi}，F(xiàn)=F{fi}，temp0=temp0∪H(fi)，F(xiàn)F0=FF0∪H(fi)，F(xiàn)=FH(fi)；若結(jié)點(diǎn)fi必定不在精確覆蓋集合中，此時temp0=temp0∪{fi}，F(xiàn)F0=FF0∪{fi}，F(xiàn)=F{fi}；按上述方法處理之后，若集合F中沒有結(jié)點(diǎn)，則整個算法結(jié)束；否則，調(diào)用回溯子算法Backtrack(i+1)進(jìn)入左子樹；

(2)返回二叉樹上一層前恢復(fù)FF0=FF0 emp0、FF1=FF1 emp1和F=F∪temp0∪temp1；

(3)情況2：假設(shè)結(jié)點(diǎn)fm不在精確覆蓋集合中，令局部集合變量temp0={}，temp1={}，此時檢查(F1∪FF1∪F){fm}是否覆蓋元素子集X中的所有元素，若不能覆蓋，說明這種情況下沒有可行解，則剪枝，不進(jìn)入右子樹，結(jié)束回溯子算法Backtrack(i)；若能覆蓋，說明這種情況下有可行解，此時temp0=temp0∪{fm}，F(xiàn)F0=FF0∪{fm}，F(xiàn)=F{fm}，在二分圖中刪除結(jié)點(diǎn)fm及其相關(guān)聯(lián)的邊。利用性質(zhì)1到性質(zhì)6對于F中的結(jié)點(diǎn)進(jìn)行降階處理，若結(jié)點(diǎn)fi必定在精確覆蓋集合中，那么temp1=temp1∪{fi}，F(xiàn)F1=FF1∪{fi}，F(xiàn)=F{fi}，temp0=temp0∪H(fi)，F(xiàn)F0=FF0∪H(fi)，F(xiàn)=FH(fi)；若結(jié)點(diǎn)fi必定不在精確覆蓋集合中，此時temp0=temp0∪{fi}，F(xiàn)F0=FF0∪{fi}，F(xiàn)=F{fi}；按上述方法處理之后，若集合F中沒有結(jié)點(diǎn)，則整個算法結(jié)束；否則，調(diào)用回溯子算法Backtrack(i+1)進(jìn)入右子樹；

(4)返回二叉樹上一層前恢復(fù)FF0=FF0 emp0、FF1=FF1 emp1和F=F∪temp0∪temp1。

算法結(jié)束后，集合F1∪FF1即是精確覆蓋問題的一個最優(yōu)解。

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

傳統(tǒng)分析方法以二分圖集合子集F中結(jié)點(diǎn)的個數(shù)k來分析算法的時間復(fù)雜度。T(k)為搜索樹產(chǎn)生的葉子結(jié)點(diǎn)個數(shù)，其中k在求解算法中的Step 7中定義為k=|F|，則該算法有如下遞推公式：

T(k)=T(k-1)+T(k-3)

(1)

其中T(k-1)代表被選中的結(jié)點(diǎn)fm不在精確覆蓋集合中，此時在圖中僅刪除結(jié)點(diǎn)fm，因此問題規(guī)模減少1；T(k-3)代表被選中的結(jié)點(diǎn)fm在精確覆蓋集合中，因此在二分圖中刪除結(jié)點(diǎn)fm，并將H(fm)中的結(jié)點(diǎn)一并刪除，由算法及性質(zhì)7可知與結(jié)點(diǎn)fm存在交集的結(jié)點(diǎn)集H(fm)中的元素個數(shù)大于等于2，因此問題規(guī)模至少減少3。

根據(jù)1.4節(jié)介紹的方法求解T(k)，即求方程x3=x2+1在1與2之間的最大解，解得x≈1.4656，因此T(k)=1.4656k,由此可以得出采用傳統(tǒng)方法得到的時間復(fù)雜度為O(1.4656k)。

2.3 加權(quán)分治方法的時間復(fù)雜度

為了降低該算法的時間復(fù)雜度，下面采用加權(quán)分治方法來分析該算法在最壞情況下的時間復(fù)雜度。

與前面?zhèn)鹘y(tǒng)分析方法不同，加權(quán)分治方法不是以集合F中結(jié)點(diǎn)的個數(shù)k作為問題的規(guī)模，而是首先給集合F中的每個結(jié)點(diǎn)賦予一個小于等于1的權(quán)值，然后以集合F中所有結(jié)點(diǎn)的權(quán)值之和W作為問題的規(guī)模來進(jìn)行時間復(fù)雜度分析，具體操作步驟見下面的介紹。

從算法的操作可以看出，該算法的時間復(fù)雜度主要與g(fi)的個數(shù)有關(guān)，因此可以根據(jù)g(fi)的個數(shù)設(shè)置相應(yīng)的權(quán)值，顯然對于g(fi)值越大的結(jié)點(diǎn)所賦予的權(quán)值應(yīng)該越大，具體如下：

(1)對于g(fi)=0的結(jié)點(diǎn)，設(shè)置權(quán)值為：h0=0；

(2)對于g(fi)=1的結(jié)點(diǎn)，設(shè)置權(quán)值為：h1=0.65；

(3)對于g(fi)=2的結(jié)點(diǎn)，設(shè)置權(quán)值為：h2=0.95；

(4)對于g(fi)≥3的結(jié)點(diǎn)，設(shè)置權(quán)值為：h≥3=1；

設(shè)Δh=hi-hi-1，其中i≥1。

為了方便計(jì)算二分圖中集合子集F的權(quán)值之和W，設(shè)二分圖集合子集F中權(quán)值為hi的結(jié)點(diǎn)個數(shù)為ki，則W的計(jì)算公式如下：

W=0.65×k1+0.95×k2+k≥3≤k

(2)

該算法中的關(guān)鍵步驟是Step 7中的回溯子算法，設(shè)n1，n2，n≥3分別為H(fi)中g(shù)(fi)值分別為1，2和大于等于3的結(jié)點(diǎn)的個數(shù)，例如n2表示H(fi)中g(shù)(fi)值為2的結(jié)點(diǎn)個數(shù)。

下面分析在回溯子算法中兩種不同的情況下問題規(guī)模W的減少量：

分支1結(jié)點(diǎn)fm在精確覆蓋集合中，此時將結(jié)點(diǎn)fm以及與fm存在交集的集合H(fm)從圖中刪除，此時整個問題的規(guī)模減少量為C1, 其計(jì)算公式為:

C1=0.95+0.65×n1+0.95×n2+n≥3

(3)

在公式(3)中，0.95表示結(jié)點(diǎn)fm自身的g(fm)對應(yīng)的權(quán)值，因?yàn)間(fm)≥2，因此權(quán)值至少為0.95；0.65×n1代表H(fm)中g(shù)(fi)=1的結(jié)點(diǎn)的總權(quán)值；0.95×n2代表H(fm)中g(shù)(fi)=2的結(jié)點(diǎn)的總權(quán)值；n≥3代表H(fm)中g(shù)(fi)≥3的結(jié)點(diǎn)的總權(quán)值。

分支2結(jié)點(diǎn)fm不在精確覆蓋集合中，此時將結(jié)點(diǎn)fm從圖中刪除，H(fm)中所有結(jié)點(diǎn)的g(fi)值都減少1，此時整個問題的規(guī)模減少量為C2，其計(jì)算公式為:

C2=0.95+(0.65-0)×n1+

(0.95-0.65)×n2+(1-0.95)×n3

(4)

在公式(4)中，0.95表示結(jié)點(diǎn)fm自身的g(fm)對應(yīng)的權(quán)值，因?yàn)間(fm)≥2，因此權(quán)值至少為0.95；(0.65-0)×n1代表刪除fm后H(fm)中原來g(fi)=1的結(jié)點(diǎn)的權(quán)值減少量；(0.95-0.65)×n2代表刪除fm后H(fm)中原來g(fi)=2的結(jié)點(diǎn)的權(quán)值減少量；(1-0.95)×n3代表刪除fm后H(fm)中原來g(fi)=3的結(jié)點(diǎn)的權(quán)值減少量；當(dāng)i≥4時，總有Δh=0。

因此，以集合F中所有結(jié)點(diǎn)權(quán)值之和W作為問題的規(guī)模來分析時間復(fù)雜度，有如下遞推公式：

T(W)=T[W-(0.95+0.65×n1+0.95×n2+n≥3)]+

T[W-(0.95+0.65×n1+0.3×n2+0.05×n3)]

(5)

下面分情況來分析該遞推方程的時間復(fù)雜度。

情況1當(dāng)g(fm)=1時，由性質(zhì)7可知，其時間復(fù)雜度為多項(xiàng)式時間。

情況2當(dāng)g(fm)=2時，此時n≥3=0，我們可以根據(jù)公式(5)分情況來計(jì)算該算法的時間復(fù)雜度，計(jì)算過程及結(jié)果如表1所示。

表1 g(fm)=2的結(jié)點(diǎn)進(jìn)行分支的遞推式

由表1可知，情況2下最壞的時間復(fù)雜度為O(1.3842w)，由于w≤k，因此情況2下最壞的時間復(fù)雜度為O(1.3842k)。

情況3當(dāng)g(fm)=3時，此時n>3=0，我們可以根據(jù)公式(5)分情況來計(jì)算該算法的時間復(fù)雜度，計(jì)算過程及結(jié)果如表2所示。

表2 g(fm)=3的結(jié)點(diǎn)進(jìn)行分支的遞推式

由表2可知，情況3下最壞的時間復(fù)雜度為O(1.3562w)，由于w≤k，因此情況3下最壞的時間復(fù)雜度為O(1.3562k)。

情況4當(dāng)g(fm)≥4時，最壞情況下的時間復(fù)雜度遞推公式如(6)所示：

T(W)=T(W-1)+T(W-5)

(6)

根據(jù)傳統(tǒng)方法計(jì)算可得T(W)=O(1.3247k)，此時不采用加權(quán)分治方法計(jì)算。

綜合4種情況可知，該算法在最壞情況下的時間復(fù)雜度為O(1.3842k)，而在不采用加權(quán)分治方法情況下的時間復(fù)雜度為O(1.4656k)。

由于算法的比較分析需要用到下面介紹的示例，因此下面先介紹示例分析，然后再給出本文算法與其它精確算法的對比分析。

2.4 示例分析

為了更清楚的說明算法原理及實(shí)際應(yīng)用情況，下面給出一個小規(guī)模示例進(jìn)行說明。

【示例1】如圖1所示，現(xiàn)有8個候選集散中心與10個待覆蓋區(qū)域，由于運(yùn)營成本和交通運(yùn)輸條件的限制，每個集散中心覆蓋若干個區(qū)域，若集散中心fi能覆蓋待覆蓋區(qū)域j，那么fi與待覆蓋區(qū)域j之間連一條邊，為了降低經(jīng)營成本，現(xiàn)從所有候選集散中心中選取若干個，使得區(qū)域全覆蓋，并且使集散中心之間沒有重復(fù)覆蓋的區(qū)域。集散中心與待覆蓋區(qū)域由二分圖來表示，如圖1所示。

圖1 集散中心與待覆蓋區(qū)域示例圖

對上述問題的計(jì)算過程可描述如下：

(1)根據(jù)性質(zhì)3，移除結(jié)點(diǎn)f1，從二分圖中刪除結(jié)點(diǎn)f1及N[f1]并且刪除其相關(guān)聯(lián)的邊；

(2)根據(jù)性質(zhì)5，結(jié)點(diǎn)f6必定在精確覆蓋集合中，將結(jié)點(diǎn)f6加入集合F1，從二分圖中刪除結(jié)點(diǎn)f6及N[f6]并且刪除其相關(guān)聯(lián)的邊；

(3)根據(jù)性質(zhì)6，結(jié)點(diǎn)f3必定在精確覆蓋集合中，將結(jié)點(diǎn)f3加入集合F1，H(f3)={f4},結(jié)點(diǎn)f4一定不在精確覆蓋集合中，將結(jié)點(diǎn)f4加入集合F0，從二分圖中刪除結(jié)點(diǎn)f3和f4及N[f3]并且刪除其相關(guān)聯(lián)的邊；

(4)根據(jù)數(shù)學(xué)性質(zhì)降階處理后，問題的規(guī)模如圖2所示，此時問題變?yōu)樵诮惦A后的集合F中尋找若干個集散中心覆蓋剩余5個待覆蓋區(qū)域。

(5)進(jìn)入回溯子算法，求解所有可行解的處理過程如圖3所示，圖3圓圈中的數(shù)字表示對應(yīng)子樹的問題規(guī)模(以結(jié)點(diǎn)的個數(shù)為問題的規(guī)模)。為了方便敘述，我們設(shè)fi=1表示將fi放入精確覆蓋集合中，fi=0表示不將fi放入精確覆蓋集合中。

具體過程如下：

①首先計(jì)算集合F中所有結(jié)點(diǎn)的g(fi)值，從中取出g(fi)值最大的結(jié)點(diǎn)f2，g(f2)=3，假設(shè)結(jié)點(diǎn)f2在精確覆蓋集合中，檢查發(fā)現(xiàn)(F1∪FF1∪F)H(f2)不能覆蓋所有區(qū)域，說明這種情況下沒有可行解，剪枝，進(jìn)入右子樹；

②假設(shè)結(jié)點(diǎn)f2不在精確覆蓋集合中，檢查發(fā)現(xiàn)(F1∪FF1∪F){f2}可以覆蓋所有區(qū)域，說明這種情況下可能有可行解，接著利用性質(zhì)1到6對問題進(jìn)行處理，根據(jù)性質(zhì)5，結(jié)點(diǎn)f8一定在精確覆蓋集合中，又因?yàn)镠(f8)={f7},結(jié)點(diǎn)f7一定不在精確覆蓋集合中；

③繼續(xù)調(diào)用回溯子算法向下一層搜索，集合F中僅剩下結(jié)點(diǎn)f5，此時假設(shè)結(jié)點(diǎn)f5在精確覆蓋集合中，到達(dá)葉子結(jié)點(diǎn)，檢查發(fā)現(xiàn)F1∪FF1覆蓋所有區(qū)域，回溯子算法結(jié)束。{f3,f5,f6,f8}即是該問題的一個最優(yōu)解。若結(jié)點(diǎn)f5不在精確覆蓋集合中，則不能覆蓋所有區(qū)域。

示例1采用本文算法時，由于利用數(shù)學(xué)性質(zhì)縮減了問題的規(guī)模，降低了算法的時間復(fù)雜度，因此搜索樹只有3個分支。

下面以圖4為例來說明加權(quán)分治方法的原理和分析過程，圖4圓圈中的數(shù)字表示對應(yīng)子樹的問題規(guī)模(以結(jié)點(diǎn)的權(quán)值之和為問題的規(guī)模)。

圖4 加權(quán)分治技術(shù)處理后的搜索樹

3 與其它算法的對比分析

近年來，國內(nèi)外研究精確覆蓋問題主要有兩種方式：啟發(fā)式算法和精確算法，啟發(fā)式算法可以快速得到可行解，但是無法保證所得解為最優(yōu)解，也不能提供解的近似比，因此得到的解往往比精確算法的解要差。

精確算法的比較一般從最壞情況下的時間復(fù)雜度、具體示例的葉子結(jié)點(diǎn)個數(shù)(葉子結(jié)點(diǎn)個數(shù)等同分支數(shù)量)、算法軟件求解具體示例的計(jì)算時間等3個方面進(jìn)行比較，其中第1個方面的比較是最重要的，因?yàn)檫@個從理論上保證了即使碰到某算法最難求解的具體示例,其理論的計(jì)算工作量也會小于最壞情況下的時間復(fù)雜度。X算法是目前求解精確覆蓋問題最常用的算法，該算法的詳細(xì)情況參見文獻(xiàn)[1]，下面分別從上述3個角度對本文算法與X算法進(jìn)行比較分析。

3.1 時間復(fù)雜度比較

設(shè)T(k)為X算法搜索樹產(chǎn)生的葉子結(jié)點(diǎn)個數(shù)，其中k為集合子集F中結(jié)點(diǎn)的個數(shù)，則該算法的遞推公式如(7)所示：

T(k)=T(k-1)+T(k-2)

(7)

其中T(k-1)代表被選中的結(jié)點(diǎn)fi不在精確覆蓋集合中，此時僅刪除結(jié)點(diǎn)fi，因此問題規(guī)模減少1；T(k-2)代表被選中的結(jié)點(diǎn)fi在精確覆蓋集合中，此時刪除結(jié)點(diǎn)fi，由于與結(jié)點(diǎn)fi存在交集的結(jié)點(diǎn)個數(shù)至少為1個，所以問題規(guī)模至少減少2。

由1.4節(jié)的通用遞推公式得T(k)=1.6181k，由此可以得出X算法的時間復(fù)雜度為O(1.6181k)。

本文算法使用了加權(quán)分治技術(shù)，由前面的分析可知，在最壞情況下的時間復(fù)雜度為O(1.3842k)。

當(dāng)集合數(shù)量為k時，X算法在最壞情況下的時間復(fù)雜度為O(1.6181k)，也就說此時搜索樹中最多有1.6181k個分支；本文算法在最壞情況下的時間復(fù)雜度為O(1.3842k)，也就說此時搜索樹中最多有1.3842k個分支；由于當(dāng)k>0時，1.3842k<1.6181k，所以對于最壞情況下的分支數(shù)，本文算法是小于X算法的。例如，當(dāng)k=20時，X算法的分支數(shù)最多可能有1.618120≈15140，而本文算法的分支數(shù)最多可能有1.384220≈667，667遠(yuǎn)小于15140。因此，求解同一個算例時，在最壞情況下，本文算法產(chǎn)生的分支數(shù)遠(yuǎn)小于X算法的分支數(shù)。

3.2 具體示例的分支數(shù)量比較

具體示例分支數(shù)量的比較以前面的示例1為例，本文算法的分支數(shù)量見2.4節(jié)圖3。

X算法對示例1求解所有可行解的處理過程的二叉樹如圖5所示：

圖5 解空間的搜索樹

在圖3和圖5中，每個葉子結(jié)點(diǎn)對應(yīng)一個分支，由圖3可知，本文算法共有3個分支，由圖5可知，X算法共有6個分支；由此可知，兩個精確算法求解該示例時，本文算法的分支數(shù)小于X算法的分支數(shù)。

3.3 算法軟件包求解實(shí)例對比

為了比較2個精確算法對具體實(shí)例的計(jì)算時間和分支數(shù)量，采用C++編程實(shí)現(xiàn)本文算法和X算法，在CPU為Intel Core i5- 4210M 2.6GHz，內(nèi)存為4.00GB的計(jì)算機(jī)上進(jìn)行試驗(yàn)。下面在表3中給出2個算法對一組隨機(jī)問題實(shí)例的計(jì)算時間和分支數(shù)量，其中集合數(shù)量為n，待覆蓋元素個數(shù)為m。

表3 求解時間和分支數(shù)量

上述實(shí)驗(yàn)表明：在小規(guī)模算例中，本文算法的求解時間稍慢于X算法，分支數(shù)量也稍多于X算法，因?yàn)樵谛∫?guī)模算例中，搜索策略與數(shù)學(xué)性質(zhì)的作用效果甚微且需要耗費(fèi)比較多的時間。隨著問題規(guī)模的增大，搜索策略與數(shù)學(xué)性質(zhì)的優(yōu)勢逐漸凸顯，因此對于大多數(shù)大規(guī)模問題實(shí)例，本文算法的求解時間和分支數(shù)量都優(yōu)于X算法。

本文算法編寫的程序運(yùn)行時間與集合數(shù)量m有較大的關(guān)系，測試的結(jié)果表明，在一般情況下，集合數(shù)量在5000以內(nèi)時，大多數(shù)算例都可以在一個小時內(nèi)求解。

4 結(jié)論

本文針對精確覆蓋問題，首先研究該問題的數(shù)學(xué)性質(zhì)，利用數(shù)學(xué)性質(zhì)對問題進(jìn)行降階，縮小問題的規(guī)模，這些數(shù)學(xué)性質(zhì)不僅能用到本文的算法設(shè)計(jì)中，而且可以用到精確覆蓋問題的其它各種算法設(shè)計(jì)中，達(dá)到加快算法執(zhí)行速度或提高算法求解效果的目的；然后根據(jù)數(shù)學(xué)性質(zhì)設(shè)計(jì)出一個基于分支降階的回溯算法求解該問題；最后在不改變算法本身的情況下，分別運(yùn)用常規(guī)技術(shù)和加權(quán)分治技術(shù)分析該算法的時間復(fù)雜度。分析的結(jié)果表明運(yùn)用加權(quán)分治技術(shù)得到的時間復(fù)雜度相對于常規(guī)分析更加精確，使算法的時間復(fù)雜度從O(1.4656k)降低到O(1.3842k)，從而獲得了更好的效果。文章最后通過與其他精確算法的對比分析，表明本文介紹的精確算法不僅在理論上具有優(yōu)勢，而且在大多數(shù)大規(guī)模實(shí)例求解中具有計(jì)算時間少的優(yōu)點(diǎn)。