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

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

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

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