s-路徑頂點(diǎn)覆蓋問(wèn)題的算法研究.pdf

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

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

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