科学技术与工程
科學技術與工程
과학기술여공정
SCIENCE TECHNOLOGY AND ENGINEERING
2014年
16期
94-101
,共8页
无向图%最小控制集%群集策略算法%扰动%贪心算法%基于禁忌搜素的模拟退火算法
無嚮圖%最小控製集%群集策略算法%擾動%貪心算法%基于禁忌搜素的模擬退火算法
무향도%최소공제집%군집책략산법%우동%탐심산법%기우금기수소적모의퇴화산법
undirected graph%minimum dominating set%cluster strategy algorithm%disturbance greedy algorithm%simulated annealing algorithm based on tabu search
图的最小控制集是一个经典的NP完全问题,其广泛应用在生物信息学、计算机通讯、工程设计等方面.目前搜索最小控制集算法有多种,例如:贪心算法、模拟退火算法、基于禁忌搜索的模拟退火算法等.当搜索结构复杂的多点图时,很多算法的搜索效果并不好.为了提高搜索效果,提出并实现一种群集策略智能算法;同时还对群集策略算法进行了非常重要的扰动改进.为了验证算法的搜索效果,利用Petersen图和随机图完成了对群集策略算法的搜索测试实验;同时也完成了对群集策略算法、贪心算法、基于禁忌搜索的模拟退火算法的比较测试实验,通过实验结果也验证了群集策略算法搜索效果最好.
圖的最小控製集是一箇經典的NP完全問題,其廣汎應用在生物信息學、計算機通訊、工程設計等方麵.目前搜索最小控製集算法有多種,例如:貪心算法、模擬退火算法、基于禁忌搜索的模擬退火算法等.噹搜索結構複雜的多點圖時,很多算法的搜索效果併不好.為瞭提高搜索效果,提齣併實現一種群集策略智能算法;同時還對群集策略算法進行瞭非常重要的擾動改進.為瞭驗證算法的搜索效果,利用Petersen圖和隨機圖完成瞭對群集策略算法的搜索測試實驗;同時也完成瞭對群集策略算法、貪心算法、基于禁忌搜索的模擬退火算法的比較測試實驗,通過實驗結果也驗證瞭群集策略算法搜索效果最好.
도적최소공제집시일개경전적NP완전문제,기엄범응용재생물신식학、계산궤통신、공정설계등방면.목전수색최소공제집산법유다충,례여:탐심산법、모의퇴화산법、기우금기수색적모의퇴화산법등.당수색결구복잡적다점도시,흔다산법적수색효과병불호.위료제고수색효과,제출병실현일충군집책략지능산법;동시환대군집책략산법진행료비상중요적우동개진.위료험증산법적수색효과,이용Petersen도화수궤도완성료대군집책략산법적수색측시실험;동시야완성료대군집책략산법、탐심산법、기우금기수색적모의퇴화산법적비교측시실험,통과실험결과야험증료군집책략산법수색효과최호.
