社交網(wǎng)絡(luò)中最小正影響支配集問題是一個NP難度的組合優(yōu)化問題,針對該問題,目前有2種典型的貪心求解算法求解速度較快,但貪心解的質(zhì)量卻有待提高。輪轉(zhuǎn)貪心策略是在不增加貪心算法時間復(fù)雜度的前提下提升貪心解的質(zhì)量,且通過實驗研究表明能有效增強一些NP難度問題效果的貪心算法。本文將輪轉(zhuǎn)貪心策略求解正影響支配集的2個貪心算法進行融合來提升貪心算法解的質(zhì)量,提出相應(yīng)的輪轉(zhuǎn)貪心算法。實驗表明,在典型的真實社交網(wǎng)絡(luò)實例上,與原有貪心算法相比,本文的輪轉(zhuǎn)貪心算法所獲解的質(zhì)量有一定的提高。 

【文章來源】：計算機與現(xiàn)代化. 2020,(09)

【文章頁數(shù)】：6 頁

【部分圖文】：

輪轉(zhuǎn)貪心策略示意圖（假設(shè)|S|=t，α=1，β=（t-k）/t)

【參考文獻】：
期刊論文
[1]無線傳感器網(wǎng)絡(luò)中干擾最小化問題的后悔貪心算法[J]. 孫佩歆.  計算機工程與科學(xué). 2017(12)
[2]社交網(wǎng)絡(luò)中求最小正影響支配集的改進算法[J]. 麥飛,陳衛(wèi)東.  華南師范大學(xué)學(xué)報(自然科學(xué)版). 2016(03)

博士論文
[1]若干支配集優(yōu)化問題求解的方法研究[D]. 袁福宇.東北師范大學(xué) 2019



本文編號：3553275