求解推廣k-CARD問題的一種變鄰域搜索方法

k-CARD問題是在一個無向網(wǎng)絡(luò)G中尋找一棵k條邊的子樹,使得這棵樹的權(quán)和最小.目前有很多啟發(fā)式算法用來解決這類NP難問題.一般的研究都只考慮點(diǎn)帶權(quán)或邊帶權(quán)的k-CARD問題.將k-CARD問題進(jìn)行推廣,考慮邊和點(diǎn)都帶權(quán)的情況.該推廣模型不僅統(tǒng)一了傳統(tǒng)的邊或點(diǎn)帶權(quán)的問題,更重要的是,它在現(xiàn)實(shí)中有著一定的應(yīng)用背景.針對推廣模型的特點(diǎn),提出了一種變鄰域搜索(VNS)方法進(jìn)行求解.數(shù)值實(shí)驗(yàn)結(jié)果表明此VNS方法求解推廣k-CARD問題是有效的.

作 者： 吳仆 蔣建林 文杰 WU Pu JIANG Jian-lin WEN Jie   作者單位： 南京航空航天大學(xué),理學(xué)院,江蘇,南京,211100  刊 名： 貴州大學(xué)學(xué)報(bào)（自然科學(xué)版）  ISTIC 英文刊名： JOURNAL OF GUIZHOU UNIVERSITY(NATURAL SCIENCE)  年，卷(期)： 2009 26(5)  分類號： O221  關(guān)鍵詞： 推廣k-CARD   變鄰域搜索   NP難   啟發(fā)式算法  

【求解推廣k-CARD問題的一種變鄰域搜索方法】相關(guān)文章：

具有語言評價(jià)信息的指派問題的求解方法04-27

具有多種形式信息的指派問題的求解方法04-27

求解接觸問題的一種新的實(shí)驗(yàn)誤差法04-27

求解探測概率門限因子的一種重要度抽樣方法04-27

一種改進(jìn)的天基測向初定軌初值和模型求解方法04-26

一種建立分區(qū)變分原理的新方法04-27

帶摩擦阻尼的葉片響應(yīng)求解方法04-27

一種改進(jìn)的蟻群算法用于灰色約束非線性規(guī)劃問題求解04-26

相干結(jié)構(gòu)中特征值積分方程求解的一種新方法04-26

用系統(tǒng)論的方法求解李約瑟難題04-27