计算机工程与应用
計算機工程與應用
계산궤공정여응용
Computer Engineering and Applications
2015年
23期
78-81,148
,共5页
支配集%禁忌搜索%组合优化
支配集%禁忌搜索%組閤優化
지배집%금기수색%조합우화
dominating set%tabu search%combinatorial optimization
最小赋权支配集是一个NP困难的组合优化问题,有着广泛的应用背景.提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法.该算法采用随机贪心构造算法构造初始解,并利用快速的局部禁忌搜索算法寻找局部最优解,通过随机扰动和修复策略来搜索新的区域,以期跳出当前的局部最优解.用顶点数为800到1 000的大规模标准测试例子测试提出的算法.数值实验结果和与现存的启发式算法比较结果表明了算法是有效的.
最小賦權支配集是一箇NP睏難的組閤優化問題,有著廣汎的應用揹景.提齣瞭一箇高效的求解最小賦權支配集的迭代禁忌搜索算法.該算法採用隨機貪心構造算法構造初始解,併利用快速的跼部禁忌搜索算法尋找跼部最優解,通過隨機擾動和脩複策略來搜索新的區域,以期跳齣噹前的跼部最優解.用頂點數為800到1 000的大規模標準測試例子測試提齣的算法.數值實驗結果和與現存的啟髮式算法比較結果錶明瞭算法是有效的.
최소부권지배집시일개NP곤난적조합우화문제,유착엄범적응용배경.제출료일개고효적구해최소부권지배집적질대금기수색산법.해산법채용수궤탐심구조산법구조초시해,병이용쾌속적국부금기수색산법심조국부최우해,통과수궤우동화수복책략래수색신적구역,이기도출당전적국부최우해.용정점수위800도1 000적대규모표준측시례자측시제출적산법.수치실험결과화여현존적계발식산법비교결과표명료산법시유효적.
