| 基于禁忌搜索的模拟退火算法在最小控制集中的应用 |
| |
| 引用本文： | 钟浩,易勇.基于禁忌搜索的模拟退火算法在最小控制集中的应用[J].成都大学学报(自然科学版),2013,32(2):138-141. |
| |
| 作者姓名： | 钟浩 易勇 |
| |
| 作者单位： | 西华大学数学与计算机学院,四川成都610039;成都大学信息科学与技术学院,四川成都610106;成都大学信息科学与技术学院,四川成都,610106 |
| |
| 基金项目： | 成都市物流公共信息服务平台建设研究基金 |
| |
| 摘 要： | 图的控制集问题是在给定的简单无向图中求出阶数最小的控制点的集合，目前它已被证明是一个NP-完全问题．针对现阶段已有的模拟退火算法提出了一种改进的基于禁忌搜索的模拟退火算法，并通过与贪心算法、传统模拟退火算法进行比较，证明了该算法可以获得较小的控制集阶数．
|
| 关 键 词： | 图 控制集 模拟退火 禁忌搜索 NP-完全 |
Application of Simulated Annealing Algorithm Based on Taboo Search in Minimal Dominating Sets |
| |
| ZHONG Hao
,
YI Yong.Application of Simulated Annealing Algorithm Based on Taboo Search in Minimal Dominating Sets[J].Journal of Chengdu University (Natural Science),2013,32(2):138-141. |
| |
| Authors: | ZHONG Hao YI Yong |
| |
| Institution: | 1.School of Mathematics and Computer Engineering,Xihua University,Chengdu 610039,China;2.School of Information Science and Technology,Chengdu University,Chengdu 610106,China) |
| |
| Abstract: | The graph dominating set problem is one about finding the dominating sets with minimal order in a given simple undirected graph, which is known to be N-P-complete problem.A simulated annealing algo- rithm based on taboo search is proposed to improve the present simulated algorithm. Compared with the greedy algorithm and traditional simulated annealing algorithm, this algorithm can get smaller dominating set order. |
| |
| Keywords: | graph dominating sets simulated annealing taboo search NP-eomplete |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
