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

Variable Neighborhood Search for an Extended K-Cardinality Tree Problem

作　　者：吴仆[1] 蒋建林[1] 文杰[1] 

机构地区：[1]南京航空航天大学理学院,江苏南京211100

出　　处：《贵州大学学报（自然科学版）》2009年第5期23-27,共5页Journal of Guizhou University:Natural Sciences

摘　　要：k-CARD问题是在一个无向网络G中寻找一棵k条边的子树,使得这棵树的权和最小。目前有很多启发式算法用来解决这类NP难问题。一般的研究都只考虑点带权或边带权的k-CARD问题。将k-CARD问题进行推广,考虑边和点都带权的情况。该推广模型不仅统一了传统的边或点带权的问题,更重要的是,它在现实中有着一定的应用背景。针对推广模型的特点,提出了一种变邻域搜索(VNS)方法进行求解。数值实验结果表明此VNS方法求解推广k-CARD问题是有效的。The minimum k -cardinality tree problem on graph G consists in finding a subtree of G with exactly k edges whose sum of weights is minimum. A number of heuristic methods have been developed recently to solve this NP-hard problem. In general, only vertex-weights or edge-weights are considered. In this paper, an extend- ed k-CARD problem is considered whose edges and vertex are both weighted. This extended model unifies vertex-weights and edge-weights problem, and more importantly, it has a certain application in practice. Based on the characteristics of this problem, a modified variable neighborhood search method （VNS） is proposed for solving it. Preliminary numerical results are reported, which show that this modified VNS method is effective for the extended k -CARD problem.

关 键 词：推广k—CARD 变邻域搜索 NP难 启发式算法 

分 类 号：O221[理学—运筹学与控制论]