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