求解推广k-CARD问题的一种变邻域搜索方法

• 作者: 吴仆 文杰 蒋建林
• 来源期刊: 贵州大学学报（自然科学版）
• 学科: 数学
• 关键词: 推广k-CARD 变邻域搜索 NP难 启发式算法
• 年，卷（期）: 2009,（5）
• 所属期刊栏目: 基础科学研究及应用
• 页码范围: 23-27
• 页数: 5页
• 分类号: O221
• 字数: 4713字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5269.2009.05.008

摘要

k-CARD问题是在一个无向网络G中寻找一棵k条边的子树,使得这棵树的权和最小.目前有很多启发式算法用来解决这类NP难问题.一般的研究都只考虑点带权或边带权的k-CARD问题.将k-CARD问题进行推广,考虑边和点都带权的情况.该推广模型不仅统一了传统的边或点带权的问题,更重要的是,它在现实中有着一定的应用背景.针对推广模型的特点,提出了一种变邻域搜索(VNS)方法进行求解.数值实验结果表明此VNS方法求解推广k-CARD问题是有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋建林	南京航空航天大学理学院	15	52	4.0	6.0
2	文杰	南京航空航天大学理学院	15	108	7.0	9.0
3	吴仆	南京航空航天大学理学院	3	13	3.0	3.0