帶有度約束的最小生成樹(shù)問(wèn)題存在于工業(yè)界的很多應(yīng)用場(chǎng)景中,如電路芯片設(shè)計(jì)、通信工程、運(yùn)輸工程、管道工程、排水系統(tǒng)等領(lǐng)域。此外,帶有度約束的最小生成樹(shù)問(wèn)題與很多重要的問(wèn)題有著千絲萬(wàn)縷的關(guān)系,例如當(dāng)生成樹(shù)的度約束變得極為松弛時(shí),該問(wèn)題就轉(zhuǎn)變成圖論中常見(jiàn)的最小生成樹(shù)問(wèn)題;然而當(dāng)生成樹(shù)中的每一個(gè)頂點(diǎn)的度約束固定為2時(shí),該問(wèn)題則轉(zhuǎn)變?yōu)榻?jīng)典的旅行商問(wèn)題。從計(jì)算復(fù)雜度方面來(lái)講,帶有度約束的最小生成樹(shù)問(wèn)題已被證明為NP難度問(wèn)題,因此不存在多項(xiàng)式時(shí)間復(fù)雜度的精確算法對(duì)其進(jìn)行求解。本文將圍繞求解有度約束的最小生成樹(shù)問(wèn)題的高效啟發(fā)式算法展開(kāi)研究。針對(duì)帶有度約束的最小生成樹(shù)問(wèn)題的特殊問(wèn)題結(jié)構(gòu),本文提出一種基于多目標(biāo)的禁忌搜索算法對(duì)其進(jìn)行求解。本文的主要工作和創(chuàng)新點(diǎn)包括:首先將關(guān)于度的硬約束條件轉(zhuǎn)換為目標(biāo)函數(shù)中的一級(jí)目標(biāo),使原問(wèn)題轉(zhuǎn)化為帶有二級(jí)目標(biāo)函數(shù)的最小生成樹(shù)問(wèn)題。其次,設(shè)計(jì)了基于邊交換的鄰域動(dòng)作用于求解該問(wèn)題。鄰域動(dòng)作每次盡可能改進(jìn)目標(biāo)函數(shù)中的一級(jí)目標(biāo)或者二級(jí)目標(biāo),提高了算法的搜索效率。再次,提出了禁忌搜索策略,以達(dá)到搜索到全局最優(yōu)解的目的。當(dāng)滿足解禁策略時(shí),則采用解禁策略接受禁忌動(dòng)作。最后,采用所提出了的... 

【文章來(lái)源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：55 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

算法流程圖

圖 3-3 邊交換動(dòng)作：a)一棵生成樹(shù) b)添加邊{1,2}c)刪除邊{5,8}生成新的生成樹(shù)至此，我們完成了對(duì) DCMST 問(wèn)題硬約束的轉(zhuǎn)化、鄰域空間的定義、鄰域動(dòng)作的設(shè)計(jì)等重要問(wèn)題的討論。在簡(jiǎn)單實(shí)例中，由權(quán)重矩陣可求出該圖的最小生成樹(shù)如圖 3-4 所示，圖中只有節(jié)點(diǎn) 4 違反度約束，對(duì)每一條非樹(shù)邊進(jìn)行檢測(cè)，當(dāng)該非樹(shù)邊加入該生成樹(shù)時(shí)，在形成的環(huán)中優(yōu)先去掉減少度約束沖突的邊，然后在度約束沖突減少相同的情況下才去掉權(quán)重改變最小的邊。

【參考文獻(xiàn)】：
期刊論文
[1]A new algorithm for degree-constrained minimum spanning tree based on the reduction technique[J]. Aibing Ning a, Liang Ma a, Xiaohua Xiong b a School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China b College of Computer and Information, Shanghai Second Polytechnic University, Shanghai 201209, China.  Progress in Natural Science. 2008(04)



本文編號(hào)：3411431