s-路徑頂點覆蓋問題的算法研究.pdf

1、在計算機(jī)網(wǎng)絡(luò)中，每一個網(wǎng)絡(luò)節(jié)點都執(zhí)行著信息生成、路由選擇、信息轉(zhuǎn)發(fā)、信息接收等多項任務(wù)。但是，其中一些節(jié)點還負(fù)責(zé)執(zhí)行其它的附加任務(wù)，例如，收集和分析網(wǎng)絡(luò)中信息癱瘓的資料、丟棄來自網(wǎng)絡(luò)的攻擊信息等，稱這些執(zhí)行附加任務(wù)的節(jié)點為網(wǎng)絡(luò)觀察員。如果將網(wǎng)絡(luò)中的所有節(jié)點都設(shè)置成觀察員節(jié)點，不僅嚴(yán)重浪費網(wǎng)絡(luò)資源，還會增加建設(shè)網(wǎng)絡(luò)的成本。
　　 所以需要解決的問題是求出該網(wǎng)絡(luò)的一個規(guī)模最小的網(wǎng)絡(luò)觀察員節(jié)點子集，使得每一條通過網(wǎng)絡(luò)中s(s≥2）個節(jié)

2、點傳播的信息至少被該節(jié)點子集中的一個節(jié)點觀察到。加之受無線傳感網(wǎng)絡(luò)安全通信問題的啟發(fā)，人們提出了s-路徑頂點覆蓋這一問題。此外，無線傳感網(wǎng)絡(luò)中最優(yōu)鏈路構(gòu)造、各種網(wǎng)絡(luò)環(huán)境中監(jiān)控設(shè)備的安置等問題都可以看做是s-路徑頂點覆蓋問題在實際中的應(yīng)用。
　　 s-路徑頂點覆蓋問題是指:給定一個無向圖和一個正整數(shù)s，從該圖中找出一個規(guī)模最小的頂點子集，使得該圖中每條長度為s-1的路徑至少包含了該頂點子集中的一個頂點。該問題已經(jīng)被證明是NP-完全

3、的。
　　 本文主要利用參數(shù)化計算技術(shù)設(shè)計求解s-路徑頂點覆蓋問題的精確算法，所做工作有:
　　 1.給出一個解決樹上的s-路徑頂點覆蓋問題的最優(yōu)算法。
　　 2.利用深度有界搜索樹方法設(shè)計解決3-路徑頂點覆蓋問題的精確算法，經(jīng)過一系列的改進(jìn)，最終得到時間復(fù)雜度為O*(2.3028k)的算法。
　　 3.利用深度有界搜索樹方法設(shè)計解決4-路徑頂點覆蓋問題的精確算法，經(jīng)過一系列的改進(jìn)，最終得到時間復(fù)雜度為O