精確覆蓋問題的加權分治算法

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

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

0 引言

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

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

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

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

1 問題介紹及性質

1.1 精確覆蓋問題簡介

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

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

1.2 問題轉換

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

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

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

1.3 數學符號

為了方便描述，采用如下數學符號表示：

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

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

d(v)：結點v的度，即與結點v相關聯的邊的數目；

m：表示二分圖元素類X中的結點個數；

n：表示二分圖集合類F中的結點個數；

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

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

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

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

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

FF1：對于集合F中的結點fi，在回溯算法分情況時假設其在精確覆蓋F*中，則將其加入集合FF1；

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

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

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

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

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

1.5 數學性質

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

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

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

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

性質3在集合子集F中，對于任意兩個結點f1和f2，若N(f1)=N(f2),則可以將f1和f2中的任一結點及其關聯邊從圖中刪除。

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

性質4在集合子集F中，若任意結點fi都滿足d(fi)≤1，則該問題可以在多項式時間內解決。

證明根據性質1可以去掉集合F中所有度為0的結點，由于集合F中所有結點的度都小于等于1，所以之后只剩下度為1的結點，再利用性質3可以去掉覆蓋元素相同的結點，則二分圖中剩下的fi和xi之間必定是一一對應的關系，顯然問題可以在多項式時間內解決。

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

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

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

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

性質7在二分圖中，若結點fm是集合子集F中g(fi)值最大的結點，如果此時g(fm)≤1，則問題可在多項式時間內求解。

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

2 算法設計及復雜性分析

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

在前面數學性質的基礎上，設計如下求解算法：

Step1初始化：輸入圖G，集合X，集合F，此時F0={}，F1={}，FF0={}，FF1={};

Step2根據性質1，若在集合子集F中存在度為0的結點fi，那么該結點一定不在精確覆蓋中，F0=F0∪{fi}，F=F{fi}，同時從圖中刪除結點fi；

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

Step4根據性質5，若圖G中存在一結點fi且g(fi)= 0，則F1=F1∪{fi}，F=F{fi}，同時從圖中刪除結點集N[fi]及其相關聯的邊；

Step5根據性質6，如果圖G中存在結點xi∈X且d(xi)=1，N(xi)=fi，則F1=F1∪{fi}，F=F{fi}，同時從圖中刪除結點集N[fi]及其相關聯的邊，F0=F0∪H(fi)，F=FH(fi)，并將H(fi)中的結點及其相關聯的邊從圖中刪除；

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

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

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

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

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

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

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

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

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

算法結束后，集合F1∪FF1即是精確覆蓋問題的一個最優解。

2.2 傳統方法分析時間復雜度

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

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

(1)

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

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

2.3 加權分治方法的時間復雜度

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

與前面傳統分析方法不同，加權分治方法不是以集合F中結點的個數k作為問題的規模，而是首先給集合F中的每個結點賦予一個小于等于1的權值，然后以集合F中所有結點的權值之和W作為問題的規模來進行時間復雜度分析，具體操作步驟見下面的介紹。

從算法的操作可以看出，該算法的時間復雜度主要與g(fi)的個數有關，因此可以根據g(fi)的個數設置相應的權值，顯然對于g(fi)值越大的結點所賦予的權值應該越大，具體如下：

(1)對于g(fi)=0的結點，設置權值為：h0=0；

(2)對于g(fi)=1的結點，設置權值為：h1=0.65；

(3)對于g(fi)=2的結點，設置權值為：h2=0.95；

(4)對于g(fi)≥3的結點，設置權值為：h≥3=1；

設Δh=hi-hi-1，其中i≥1。

為了方便計算二分圖中集合子集F的權值之和W，設二分圖集合子集F中權值為hi的結點個數為ki，則W的計算公式如下：

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

(2)

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

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

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

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

(3)

在公式(3)中，0.95表示結點fm自身的g(fm)對應的權值，因為g(fm)≥2，因此權值至少為0.95；0.65×n1代表H(fm)中g(fi)=1的結點的總權值；0.95×n2代表H(fm)中g(fi)=2的結點的總權值；n≥3代表H(fm)中g(fi)≥3的結點的總權值。

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

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

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

(4)

在公式(4)中，0.95表示結點fm自身的g(fm)對應的權值，因為g(fm)≥2，因此權值至少為0.95；(0.65-0)×n1代表刪除fm后H(fm)中原來g(fi)=1的結點的權值減少量；(0.95-0.65)×n2代表刪除fm后H(fm)中原來g(fi)=2的結點的權值減少量；(1-0.95)×n3代表刪除fm后H(fm)中原來g(fi)=3的結點的權值減少量；當i≥4時，總有Δh=0。

因此，以集合F中所有結點權值之和W作為問題的規模來分析時間復雜度，有如下遞推公式：

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)

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

情況1當g(fm)=1時，由性質7可知，其時間復雜度為多項式時間。

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

表1 g(fm)=2的結點進行分支的遞推式

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

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

表2 g(fm)=3的結點進行分支的遞推式

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

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

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

(6)

根據傳統方法計算可得T(W)=O(1.3247k)，此時不采用加權分治方法計算。

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

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

2.4 示例分析

為了更清楚的說明算法原理及實際應用情況，下面給出一個小規模示例進行說明。

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

圖1 集散中心與待覆蓋區域示例圖

對上述問題的計算過程可描述如下：

(1)根據性質3，移除結點f1，從二分圖中刪除結點f1及N[f1]并且刪除其相關聯的邊；

(2)根據性質5，結點f6必定在精確覆蓋集合中，將結點f6加入集合F1，從二分圖中刪除結點f6及N[f6]并且刪除其相關聯的邊；

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

(4)根據數學性質降階處理后，問題的規模如圖2所示，此時問題變為在降階后的集合F中尋找若干個集散中心覆蓋剩余5個待覆蓋區域。

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

具體過程如下：

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

②假設結點f2不在精確覆蓋集合中，檢查發現(F1∪FF1∪F){f2}可以覆蓋所有區域，說明這種情況下可能有可行解，接著利用性質1到6對問題進行處理，根據性質5，結點f8一定在精確覆蓋集合中，又因為H(f8)={f7},結點f7一定不在精確覆蓋集合中；

③繼續調用回溯子算法向下一層搜索，集合F中僅剩下結點f5，此時假設結點f5在精確覆蓋集合中，到達葉子結點，檢查發現F1∪FF1覆蓋所有區域，回溯子算法結束。{f3,f5,f6,f8}即是該問題的一個最優解。若結點f5不在精確覆蓋集合中，則不能覆蓋所有區域。

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

下面以圖4為例來說明加權分治方法的原理和分析過程，圖4圓圈中的數字表示對應子樹的問題規模(以結點的權值之和為問題的規模)。

圖4 加權分治技術處理后的搜索樹

3 與其它算法的對比分析

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

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

3.1 時間復雜度比較

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

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

(7)

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

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

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

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

3.2 具體示例的分支數量比較

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

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

圖5 解空間的搜索樹

在圖3和圖5中，每個葉子結點對應一個分支，由圖3可知，本文算法共有3個分支，由圖5可知，X算法共有6個分支；由此可知，兩個精確算法求解該示例時，本文算法的分支數小于X算法的分支數。

3.3 算法軟件包求解實例對比

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

表3 求解時間和分支數量

上述實驗表明：在小規模算例中，本文算法的求解時間稍慢于X算法，分支數量也稍多于X算法，因為在小規模算例中，搜索策略與數學性質的作用效果甚微且需要耗費比較多的時間。隨著問題規模的增大，搜索策略與數學性質的優勢逐漸凸顯，因此對于大多數大規模問題實例，本文算法的求解時間和分支數量都優于X算法。

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

4 結論

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