發(fā)布時間：2021-09-28 06:47

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

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

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

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

【部分圖文】：

算法流程圖

圖 3-3 邊交換動作：a)一棵生成樹 b)添加邊{1,2}c)刪除邊{5,8}生成新的生成樹至此，我們完成了對 DCMST 問題硬約束的轉(zhuǎn)化、鄰域空間的定義、鄰域動作的設(shè)計等重要問題的討論。在簡單實例中，由權(quán)重矩陣可求出該圖的最小生成樹如圖 3-4 所示，圖中只有節(jié)點 4 違反度約束，對每一條非樹邊進(jìn)行檢測，當(dāng)該非樹邊加入該生成樹時，在形成的環(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)



本文編號：3411431