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

A Cluster Strategy Search for the Minimum Dominating Set Problem

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

The minimum dominating set is a typical NP complete problem and it is widely applied in bioinformatics, computer communications, engineering design, etc. There are several types of searching for the minimum dominating sets, such as： Greedy algorithm, simulated annealing algorithm and simulated annealing algorithm based on tabu search. When searching for complex-structured multi-point graph, many algorithms cannot get good results. To better the search results, a cluster strategy has been proposed and implemented and carried important improved disturbance on the cluster strategy. Taking advantage of Petersen Graph and Random Graph, the search test has been completed on cluster strategy, and compared the result of Greedy algorithm, simulated annealing algorithm and simulated annealing algorithm based on tabu search, and drew the conclusion that the research result of cluster control strategy is the best.