資源描述：
《集合覆蓋問(wèn)題的一種隨機(jī)近似算法研究》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、武漢科技大學(xué)組合數(shù)學(xué)課程論文第8頁(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)鍵詞：隨機(jī)算法；近似算法；集合覆蓋1.引言自從集合覆蓋問(wèn)題提出以來(lái)，相繼有很多學(xué)者利用不同思想提出了很多不同的算法，這些算法主要
2、分為完整算法和啟發(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)近似解一般也能夠滿(mǎn)足現(xiàn)實(shí)的要求。與上述確定算法不同，本文從概率的角度給出了集合覆蓋問(wèn)題的一種隨機(jī)算法。由于算法的隨機(jī)性，每次運(yùn)行輸出的覆蓋都是隨機(jī)的，本文證明了算法所求覆蓋費(fèi)用的期望值不超過(guò)最優(yōu)覆蓋的B倍，其中。算法每
3、次運(yùn)行輸出的覆蓋都可能不同，因此，可以多次運(yùn)行該算法得到一系列覆蓋，從中選擇費(fèi)用最小的，該覆蓋很可能接近最優(yōu)解，甚至可能就是最優(yōu)解。本算法的時(shí)間復(fù)雜度是線(xiàn)性的，這為算法的多次運(yùn)行奠定了基礎(chǔ)。另外，當(dāng)B較小的時(shí)候，本文算法可以給出比當(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ù)最少。武漢科技大學(xué)組合數(shù)學(xué)課程論文第8頁(yè)形式化描述為輸入：集合E=，S=輸出：，使得
4、，且最小。(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ī)近似算法(AlgorithmWSC_RA)如下。輸入：帶權(quán)重的集合覆蓋問(wèn)題的一個(gè)實(shí)例(E，S，W)。輸出：集合覆蓋C。第一步:以任意順序排列E中的元素；第二步：①選擇下一個(gè)元素；②從中隨機(jī)選擇x，使得③④第三步：returnC。注意到，包含元素多的集合被選中的概率較大，
5、而在每一輪循環(huán)中，算法以較大概率選擇權(quán)重較小的集合。武漢科技大學(xué)組合數(shù)學(xué)課程論文第8頁(yè)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之前已經(jīng)確定，那么算法的輸出結(jié)果和期望權(quán)重可以表達(dá)為現(xiàn)在的目
6、標(biāo)是適當(dāng)?shù)匕阉惴╓SC_RA的分析一般化?？紤]在中的集合，本文將證明這些集合是C的主要組成部分。用另外的參數(shù)表示這部分元素。定義2令為算法WSC_RA計(jì)算出的集合，同時(shí)這些集合在最優(yōu)解中。因?yàn)樵谒惴▓?zhí)行之前就已經(jīng)確定了，顯然有因此并且因?yàn)?。，所以有武漢科技大學(xué)組合數(shù)學(xué)課程論文第8頁(yè)定理2，即算法輸出解C的期望值至多是期望權(quán)重的B倍。證明：首先通過(guò)在集合覆蓋實(shí)例上做的一個(gè)游戲來(lái)描述定理的證明。假設(shè)集合覆蓋實(shí)例在開(kāi)始時(shí)，每個(gè)的初始資本為，這些權(quán)重是在算法執(zhí)行之前確定的，那么S中集合所有的資本的總和正好是算法的
7、輸出結(jié)果的期望權(quán)重。假設(shè)存在一個(gè)全局策略，在該策略下，每個(gè)集合s∈S可以分配它的全部資本到它所包含的元素上，并且每個(gè)元素能夠從包含它的集合(即L(e))中接收到相同數(shù)量的資本。然后，每個(gè)元素e向在中并且包含它的集合(即)歸還它所接收的資本。因此，如果L(e)中僅有一個(gè)集合，即，那么所接收到的資本是它所分配給e的資本的倍；如果，那么e向中的每一個(gè)集合所歸還的資本必然少于該集合所分配給e的資本的倍；如果L(e)中所有的集合都在中，那么e向中的每一個(gè)集合所歸還的資本恰好等于該集合所分配給e的資本。不難看出，經(jīng)過(guò)
8、上述處理后，每個(gè)在中的集合的資本至多增加至原來(lái)資本的倍，而沒(méi)有在中的集合破產(chǎn)了(資本為O)。由此可以看出，現(xiàn)在S中的所有資本至多是開(kāi)始時(shí)元素所擁有資本的B倍。因?yàn)槊總€(gè)集合s開(kāi)始時(shí)所擁有的資本為，可以用下式表示這個(gè)表達(dá)式與定理2中的表達(dá)式是等價(jià)的?，F(xiàn)在唯一需要說(shuō)明的是，上述把資本分配到元素的資本分配策略是存在的，為什么存在這樣的分配策略呢?考慮每個(gè)集合s∈S，如果它所包含的元素中有一個(gè)把它選擇到覆蓋C中，那么它才會(huì)在覆蓋C中。因
