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