社交网络中正影响支配集问题的轮转贪心算法

发布时间：2021-12-28 03:05

　　社交网络中最小正影响支配集问题是一个NP难度的组合优化问题,针对该问题,目前有2种典型的贪心求解算法求解速度较快,但贪心解的质量却有待提高。轮转贪心策略是在不增加贪心算法时间复杂度的前提下提升贪心解的质量,且通过实验研究表明能有效增强一些NP难度问题效果的贪心算法。本文将轮转贪心策略求解正影响支配集的2个贪心算法进行融合来提升贪心算法解的质量,提出相应的轮转贪心算法。实验表明,在典型的真实社交网络实例上,与原有贪心算法相比,本文的轮转贪心算法所获解的质量有一定的提高。 

【文章来源】：计算机与现代化. 2020,(09)

【文章页数】：6 页

【部分图文】：

轮转贪心策略示意图（假设|S|=t，α=1，β=（t-k）/t)

【参考文献】：
期刊论文
[1]无线传感器网络中干扰最小化问题的后悔贪心算法[J]. 孙佩歆.  计算机工程与科学. 2017(12)
[2]社交网络中求最小正影响支配集的改进算法[J]. 麦飞,陈卫东.  华南师范大学学报(自然科学版). 2016(03)

博士论文
[1]若干支配集优化问题求解的方法研究[D]. 袁福宇.东北师范大学 2019



本文编号：3553275