最小赋权支配集的迭代禁忌搜索算法

• 作者: 林耿
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 支配集 禁忌搜索 组合优化
• 年，卷（期）: 2015,（23）
• 所属期刊栏目: 理论研究、研发设计
• 页码范围: 78-81,148
• 页数: 5页
• 分类号: TP18|O221.4
• 字数: 5293字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1409-0069

摘要

最小赋权支配集是一个NP困难的组合优化问题,有着广泛的应用背景.提出了一个高效的求解最小赋权支配集的迭代禁忌搜索算法.该算法采用随机贪心构造算法构造初始解,并利用快速的局部禁忌搜索算法寻找局部最优解,通过随机扰动和修复策略来搜索新的区域,以期跳出当前的局部最优解.用顶点数为800到1 000的大规模标准测试例子测试提出的算法.数值实验结果和与现存的启发式算法比较结果表明了算法是有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林耿	闽江学院数学系	24	24	3.0	4.0