求解推廣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