最小控制集问题的群集策略智能算法研究

摘要：

图的最小控制集是一个经典的NP完全问题,其广泛应用在生物信息学、计算机通讯、工程设计等方面.目前搜索最小控制集算法有多种,例如:贪心算法、模拟退火算法、基于禁忌搜索的模拟退火算法等.当搜索结构复杂的多点图时,很多算法的搜索效果并不好.为了提高搜索效果,提出并实现一种群集策略智能算法;同时还对群集策略算法进行了非常重要的扰动改进.为了验证算法的搜索效果,利用Petersen图和随机图完成了对群集策略算法的搜索测试实验;同时也完成了对群集策略算法、贪心算法、基于禁忌搜索的模拟退火算法的比较测试实验,通过实验结果也验证了群集策略算法搜索效果最好.

关键词：无向图、最小控制集、群集策略算法、扰动、贪心算法、基于禁忌搜素的模拟退火算法

所属期刊栏目：14

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家青年科学基金项目61309015

在线出版日期：2014-08-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：94-101