集合覆蓋問題的一種隨機(jī)近似算法研究

1、集合覆蓋問題的一種隨機(jī)近似算法研究摘 要：集合覆蓋問題(SCP)是運(yùn)籌學(xué)中最基本的組合問題，本文給出了集合覆蓋問題的一種隨機(jī)近似算法。給定的子集的集合S和S中每個子集的權(quán)值，帶權(quán)的集合覆蓋問題是從S中選擇費(fèi)用和最小的子集使得其并集覆蓋E。對E中每一個未被覆蓋的元素，以某一精心設(shè)計的概率分布選擇包含該元素的子集，直到E中所有元素均被覆蓋，算法結(jié)束。關(guān)鍵詞：隨機(jī)算法；近似算法；集合覆蓋1.引言自從集合覆蓋問題提出以來，相繼有很多學(xué)者利用不同思想提出了很多不同的算法，這些算法主要分為完整算法和啟發(fā)式算法。完整算法基本上建立在分支定界基礎(chǔ)上。通過比較和分析，Caprara等人認(rèn)為CPLEX算法是求解S

2、CP最好的完整算法。但如果問題規(guī)模比較大時，其時間代價會非常高。而啟發(fā)式算法則以犧牲解的精度來取得較好的時間復(fù)雜度，在可接受的時間內(nèi)找到一個最優(yōu)近似解。在實際問題中，最優(yōu)近似解一般也能夠滿足現(xiàn)實的要求。與上述確定算法不同，本文從概率的角度給出了集合覆蓋問題的一種隨機(jī)算法。由于算法的隨機(jī)性，每次運(yùn)行輸出的覆蓋都是隨機(jī)的，本文證明了算法所求覆蓋費(fèi)用的期望值不超過最優(yōu)覆蓋的B倍，其中。算法每次運(yùn)行輸出的覆蓋都可能不同，因此，可以多次運(yùn)行該算法得到一系列覆蓋，從中選擇費(fèi)用最小的，該覆蓋很可能接近最優(yōu)解，甚至可能就是最優(yōu)解。本算法的時間復(fù)雜度是線性的，這為算法的多次運(yùn)行奠定了基礎(chǔ)。另外，當(dāng)B較小的時候，

3、本文算法可以給出比當(dāng)前結(jié)果較優(yōu)的解。2.算法(1)設(shè)為n個元素的集合，S= 為E的子集的集合。所謂E的覆蓋是S的一個子集C，C中元素的并集為E。經(jīng)典的集合覆蓋問題欲求E的一個覆蓋C，使得C在E的所有覆蓋中所含元素個數(shù)最少。形式化描述為輸入：集合E= ，S= 輸出：，使得，且最小。(2)帶權(quán)的集合覆蓋問題則是更一般的情況。仍設(shè) ，對有一個非負(fù)權(quán)值叫，表示選擇所需要的費(fèi)用，覆蓋C的費(fèi)用為C中元素權(quán)值的和,相應(yīng)地，問題的輸出是求最小費(fèi)用的覆蓋。形式化描述為輸人：輸出：，使得。且最小化.(3)帶權(quán)集合覆蓋問題的隨機(jī)近似算法(Algorithm WSC_RA)如下。輸入：帶權(quán)重的集合覆蓋問題的一個實例(

4、E，S，W)。輸出：集合覆蓋C。第一步:以任意順序排列E中的元素；第二步：選擇下一個元素；從中隨機(jī)選擇x，使得 第三步：return C。注意到，包含元素多的集合被選中的概率較大，而在每一輪循環(huán)中，算法以較大概率選擇權(quán)重較小的集合。3.算法近似比的分析定理1假設(shè)，其中 ，那么算法WSC_RA是一個在期望意義下近似比為B的近似算法。首先固定輸入實例(E，S，W)中元素被試探的順序，并假設(shè)是(E，S，W)的一個最優(yōu)覆蓋，通過WSC_RA算法得到的解C是S的一個隨機(jī)子集。定義1 對于任意s，定義如下一個變量X令表示X的期望值。表明了集合s實際對覆蓋C的貢獻(xiàn)，并且變量的分布和的值在執(zhí)行算法WSC_RA

5、之前已經(jīng)確定，那么算法的輸出結(jié)果和期望權(quán)重可以表達(dá)為現(xiàn)在的目標(biāo)是適當(dāng)?shù)匕阉惴╓SC_RA的分析一般化。考慮在中的集合，本文將證明這些集合是C的主要組成部分。用另外的參數(shù)表示這部分元素。定義2 令為算法WSC_RA計算出的集合，同時這些集合在最優(yōu)解中。因為在算法執(zhí)行之前就已經(jīng)確定了，顯然有因此 并且因為。，所以有定理2 ，即算法輸出解C的期望值至多是期望權(quán)重的B倍。證明：首先通過在集合覆蓋實例上做的一個游戲來描述定理的證明。假設(shè)集合覆蓋實例在開始時，每個的初始資本為，這些權(quán)重是在算法執(zhí)行之前確定的，那么S中集合所有的資本的總和正好是算法的輸出結(jié)果的期望權(quán)重。假設(shè)存在一個全局策略，在該策略下，每個

6、集合sS可以分配它的全部資本到它所包含的元素上，并且每個元素能夠從包含它的集合(即L(e)中接收到相同數(shù)量的資本。然后，每個元素e向在中并且包含它的集合(即)歸還它所接收的資本。因此，如果L(e)中僅有一個集合，即，那么所接收到的資本是它所分配給e的資本的倍；如果，那么e向中的每一個集合所歸還的資本必然少于該集合所分配給e的資本的倍；如果L(e)中所有的集合都在中，那么e向中的每一個集合所歸還的資本恰好等于該集合所分配給e的資本。不難看出，經(jīng)過上述處理后，每個在中的集合的資本至多增加至原來資本的倍，而沒有在中的集合破產(chǎn)了(資本為O)。由此可以看出，現(xiàn)在S中的所有資本至多是開始時元素所擁有資本的

7、B倍。因為每個集合s開始時所擁有的資本為，可以用下式表示這個表達(dá)式與定理2中的表達(dá)式是等價的?，F(xiàn)在唯一需要說明的是，上述把資本分配到元素的資本分配策略是存在的，為什么存在這樣的分配策略呢?考慮每個集合sS，如果它所包含的元素中有一個把它選擇到覆蓋C中，那么它才會在覆蓋C中。因此，集合s對于覆蓋費(fèi)用的貢獻(xiàn)的期望是由把它選擇到C中的元素的貢獻(xiàn)組成的。集合s中的元素以一定的概率P把它選擇到覆蓋C中，從而對C的費(fèi)用作出貢獻(xiàn)。更進(jìn)一步，元素e對于L(e)中的集合的貢獻(xiàn)大小為由此可見，每個元素e對于L(e)中的集合的貢獻(xiàn)是相同的。前面的論證是利用分配策略以一種比較明顯的方式把覆蓋C的費(fèi)用和最優(yōu)覆蓋的費(fèi)用關(guān)

8、聯(lián)起來。如果一個元素eE被算法WSC_RA考慮到，然而還沒有被覆蓋時，則稱該元素為關(guān)鍵的。關(guān)鍵元素e使得算法從L(e)中隨機(jī)地選擇一個集合添加到C中。如果隨機(jī)選擇了s到C中，則s是因為關(guān)鍵元素e而被隨機(jī)選擇到C中。定義3 對于任意元素eE和任意定義隨機(jī)變量如下注意到對于每個元素e，有且僅有一個為非o，而且對于任意的集合，至多有一個它所包含的元素可以選擇它到覆蓋C中。因此有由此可以得到雖然對于s至多有一個為非零，但是它們的期望值都可以是非零的，因為期望是建立在算法WSC_RA對所有可能的選擇的基礎(chǔ)上。需要說明的是，對于任意，任意5，這個說明隱含了所期望的分配策略的存在性。這是因為每個集合sS分配

9、價值為的資本給它所包含的元素e，因而，每個元素可以從包含它的集合接收到相同價值的資本。因此有以上的分配策略。定理3 對于任意eE，任意s，。證明 4 結(jié)束語給定圖以及定義在頂點(diǎn)上的費(fèi)用函數(shù)W，所謂頂點(diǎn)覆蓋S是頂點(diǎn)集合的一個子集，滿足對于每條邊，u和v至少有一個被S覆蓋。最小費(fèi)用頂點(diǎn)覆蓋問題是要求一個費(fèi)用最小的頂點(diǎn)覆蓋。把邊集E看成要覆蓋的對象，每個頂點(diǎn)看成它所關(guān)聯(lián)邊的集合，這樣頂點(diǎn)覆蓋問題就轉(zhuǎn)化成集合覆蓋問題。每條邊包含在2個子集中，即B=2，因此本文算法所求的頂點(diǎn)覆蓋費(fèi)用的期望值不會超過最優(yōu)頂點(diǎn)覆蓋的2倍。參考文獻(xiàn)1 金銀秋 ；最小覆蓋算法及正確性證明；計算機(jī)應(yīng)用與研究； 1993(2),39-4t2 宋恩民；求解析取范式永真性問題的一個近似快速算法；科學(xué)通報，1992(8)3