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

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

【文章頁數】：55 頁

【學位級別】：碩士

【部分圖文】：

算法流程圖

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

【參考文獻】：
期刊論文
[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