【摘要】：覆蓋問題是一類非常著名的組合優(yōu)化問題.頂點(diǎn)覆蓋問題與集合覆蓋問題,作為圖靈獎(jiǎng)獲得者Richard M.Karp提出的21個(gè)經(jīng)典NP完全問題中的兩個(gè)備受關(guān)注的問題,目前已被理論計(jì)算機(jī)科學(xué)領(lǐng)域中的廣大研究工作者所熟知,因而相關(guān)的研究工作已經(jīng)有很多.本文主要是研究這兩類問題所對應(yīng)的推廣問題連通k-路覆蓋問題(CVCPk)與部分集合多重覆蓋問題(PSMC)。連通k-路點(diǎn)覆蓋問題(CVCPk)產(chǎn)生于無線傳感網(wǎng)絡(luò)中的安全與檢測.對于一個(gè)圖G =(V,E),如果圖中的每一條k-1長路都有至少一個(gè)點(diǎn)屬于點(diǎn)集S,我們稱點(diǎn)集S是圖G的k-路點(diǎn)覆蓋,如果S在圖G中導(dǎo)出的子圖是連通的,我們就稱點(diǎn)集S是圖G的連通k-路點(diǎn)覆蓋(CVCPk)。部分集合多重覆蓋問題(PSMC)是集合多重覆蓋問題(SMC)與部分集合覆蓋問題(PSC)的結(jié)合.給定一個(gè)集合 E,實(shí)數(shù)0ρ1,以及由E的子集構(gòu)成的集簇S.對于任意集合S ∈ S都給定一個(gè)成本ws0.對于任意元素e∈E都定義一個(gè)覆蓋需求re0.集合多重覆蓋問題指的是找到一個(gè)最小的子集簇F(?)S,使得E中的每一個(gè)元素都能達(dá)到覆蓋要求,其中元素e能達(dá)到覆蓋要求指的是e屬于F的至少re個(gè)集合.部分集合多重覆蓋問題指的是找到一個(gè)最小的子集簇F'(?)S,使得E中至少ρ|E|個(gè)元素達(dá)到覆蓋要求值。本學(xué)位論文計(jì)劃分為四章,第一章介紹相關(guān)概念與背景知識,并介紹研究現(xiàn)狀.第二章,設(shè)計(jì)了一個(gè)連通3-路覆蓋問題的近似算法,其近似比為2α+ 1/2,其中α為(不加連通條件的)3-路覆蓋問題的近似比.第三章給出部分集合多重覆蓋的貪婪算法,并提出一個(gè)新的衡量算法性能的參數(shù):部分完全近似比,即將部分覆蓋的近似值與完全覆蓋的最優(yōu)值進(jìn)行比較.結(jié)果表明我們的算法部分完全近似比為lnr/1-ρ,數(shù)值實(shí)驗(yàn)也表明了用部分覆蓋替代完全覆蓋的優(yōu)點(diǎn).第四章對研究方法與研究結(jié)果進(jìn)行討論與總結(jié)。
【圖文】：

化是由R%收縮后得到的點(diǎn)所構(gòu)成的集合．對每一個(gè)收縮點(diǎn)ｓ邋ｅ邋＼／（Ｇｌｖ．＼Ｓ），我們逡逑令兒表示收縮點(diǎn)ｓ對應(yīng)到原圖Ｇ上的點(diǎn)集．我們把兒中的點(diǎn)統(tǒng)稱為標(biāo)準(zhǔn)點(diǎn)（ｎｏｍｒｎｌ逡逑ｒｅｒｈｃｅｓ）．為７便于讀者理解上述概念，，我們給出了一個(gè)例子．如圖２．１⑷，｛心，逡逑和｛＾p海梢遠(yuǎn)雜Φ酵跡牽郟櫻ⅲ葜械牧礁雋ǚ種В�；２｝和｛ｍ，ＡP梢遠(yuǎn)雜Φ酵煎義希峰義

本文編號：2593315