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

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

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

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

4、E，S，W)。輸出：集合覆蓋C。第一步:以任意順序排列E中的元素；第二步：選擇下一個(gè)元素；從中隨機(jī)選擇x，使得 第三步：return C。注意到，包含元素多的集合被選中的概率較大，而在每一輪循環(huán)中，算法以較大概率選擇權(quán)重較小的集合。3.算法近似比的分析定理1假設(shè)，其中 ，那么算法WSC_RA是一個(gè)在期望意義下近似比為B的近似算法。首先固定輸入實(shí)例(E，S，W)中元素被試探的順序，并假設(shè)是(E，S，W)的一個(gè)最優(yōu)覆蓋，通過(guò)WSC_RA算法得到的解C是S的一個(gè)隨機(jī)子集。定義1 對(duì)于任意s，定義如下一個(gè)變量X令表示X的期望值。表明了集合s實(shí)際對(duì)覆蓋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計(jì)算出的集合，同時(shí)這些集合在最優(yōu)解中。因?yàn)樵谒惴▓?zhí)行之前就已經(jīng)確定了，顯然有因此 并且因?yàn)?。，所以有定? ，即算法輸出解C的期望值至多是期望權(quán)重的B倍。證明：首先通過(guò)在集合覆蓋實(shí)例上做的一個(gè)游戲來(lái)描述定理的證明。假設(shè)集合覆蓋實(shí)例在開(kāi)始時(shí)，每個(gè)的初始資本為，這些權(quán)重是在算法執(zhí)行之前確定的，那么S中集合所有的資本的總和正好是算法的輸出結(jié)果的期望權(quán)重。假設(shè)存在一個(gè)全局策略，在該策略下，每個(gè)

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

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

8、聯(lián)起來(lái)。如果一個(gè)元素eE被算法WSC_RA考慮到，然而還沒(méi)有被覆蓋時(shí)，則稱該元素為關(guān)鍵的。關(guān)鍵元素e使得算法從L(e)中隨機(jī)地選擇一個(gè)集合添加到C中。如果隨機(jī)選擇了s到C中，則s是因?yàn)殛P(guān)鍵元素e而被隨機(jī)選擇到C中。定義3 對(duì)于任意元素eE和任意定義隨機(jī)變量如下注意到對(duì)于每個(gè)元素e，有且僅有一個(gè)為非o，而且對(duì)于任意的集合，至多有一個(gè)它所包含的元素可以選擇它到覆蓋C中。因此有由此可以得到雖然對(duì)于s至多有一個(gè)為非零，但是它們的期望值都可以是非零的，因?yàn)槠谕墙⒃谒惴╓SC_RA對(duì)所有可能的選擇的基礎(chǔ)上。需要說(shuō)明的是，對(duì)于任意，任意5，這個(gè)說(shuō)明隱含了所期望的分配策略的存在性。這是因?yàn)槊總€(gè)集合sS分配

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