三維覆蓋控制及其在無線AD HOC網(wǎng)絡(luò)中的應(yīng)用研究.pdf

1、頂點(diǎn)覆蓋問題是圖論中的經(jīng)典組合優(yōu)化問題。已被證明是NP完備的,具有較高的計(jì)算復(fù)雜性。本文主要研究無權(quán)圖與加權(quán)圖的最大獨(dú)立集,目的是為了求解最小加權(quán)頂點(diǎn)覆蓋。論文主要研究工作和成果包括以下幾個(gè)方面:
　　首先,對(duì)無權(quán)圖的頂點(diǎn)覆蓋和獨(dú)立集進(jìn)行了深入研究,在基于兩者關(guān)系的基礎(chǔ)上,得出結(jié)論,即在無權(quán)圖中,對(duì)于任意一個(gè)頂點(diǎn)判斷屬于獨(dú)立集比頂點(diǎn)覆蓋簡(jiǎn)單。接著,在鄰接矩陣與獨(dú)立集自身特性的基礎(chǔ)上,設(shè)計(jì)了一種基于鄰接矩陣求解最大獨(dú)立集的算法,進(jìn)而

2、解決最小頂點(diǎn)覆蓋。通過實(shí)驗(yàn)驗(yàn)證算法的時(shí)間復(fù)雜度和正確性。
　　其次,利用上述求解無權(quán)圖的方法,同樣從鄰接矩陣與獨(dú)立集自身特性入手,對(duì)加權(quán)圖進(jìn)行分析,并結(jié)合改進(jìn)傳統(tǒng)的貪婪算法,提出兩個(gè)概念集合,即鄰接集合和非鄰接集合,設(shè)計(jì)一種基于貪婪算法求解最大加權(quán)獨(dú)立集,進(jìn)而求解最小加權(quán)頂點(diǎn)覆蓋。同樣通過實(shí)驗(yàn)驗(yàn)證算法的正確性和可行性。
　　最后,文中對(duì)最大加權(quán)獨(dú)立集在無線Ad hoc網(wǎng)絡(luò)分簇算法方面的應(yīng)用進(jìn)行了研究。通過實(shí)驗(yàn),將最大加權(quán)獨(dú)立