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

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

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

作 者： 吴仆 蒋建林 文杰 WU Pu JIANG Jian-lin WEN Jie   作者单位： 南京航空航天大学,理学院,江苏,南京,211100  刊 名： 贵州大学学报（自然科学版）  ISTIC 英文刊名： JOURNAL OF GUIZHOU UNIVERSITY(NATURAL SCIENCE)  年，卷(期)： 2009 26(5)  分类号： O221  关键词： 推广k-CARD   变邻域搜索   NP难   启发式算法  

【求解推广k-CARD问题的一种变邻域搜索方法】相关文章：

具有语言评价信息的指派问题的求解方法04-27

具有多种形式信息的指派问题的求解方法04-27

求解接触问题的一种新的实验误差法04-27

求解探测概率门限因子的一种重要度抽样方法04-27

一种改进的天基测向初定轨初值和模型求解方法04-26

一种建立分区变分原理的新方法04-27

带摩擦阻尼的叶片响应求解方法04-27

一种改进的蚁群算法用于灰色约束非线性规划问题求解04-26

相干结构中特征值积分方程求解的一种新方法04-26

用系统论的方法求解李约瑟难题04-27