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

1、武漢科技大學(xué)組合數(shù)學(xué)課程論文第1頁(yè)集合覆蓋問(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)鍵詞關(guān)鍵詞：隨機(jī)算法；近似算法；集合覆蓋1.1.引言引言自

2、從集合覆蓋問(wèn)題提出以來(lái)，相繼有很多學(xué)者利用不同思想提出了很多不同的算法，這些算法主要分為完整算法和啟發(fā)式算法。完整算法基本上建立在分支定界基礎(chǔ)上。通過(guò)比較和分析，Caprara等人認(rèn)為CPLEX算法是求解SCP最好的完整算法。但如果問(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í)的要求。與上述確定算法不同，本文從概率的

3、角度給出了集合覆蓋問(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í)候，本文算法可以給出比當(dāng)前結(jié)果較優(yōu)的解。2.2.算法算法(1)設(shè)為n個(gè)元素的集

4、合，S=為E的子集的集合。所謂E的覆蓋是S的一個(gè)子集C，C中元素的并集為E。經(jīng)典的集合覆蓋問(wèn)題欲求E的一個(gè)覆蓋C，使得C在E的所有覆蓋中所含元素個(gè)數(shù)最少。武漢科技大學(xué)組合數(shù)學(xué)課程論文第3頁(yè)定理定理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，定義如下一

5、個(gè)變量X令表示X的期望值。表明了集合s實(shí)際對(duì)覆蓋C的貢獻(xiàn)，并且變量的分布和的值在執(zhí)行算法WSC_RA之前已經(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的