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

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

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

【部分圖文】：

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

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

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



本文編號(hào)：3553275