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

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

本文編號：2593315