約束最小生成樹(shù)算法的研究.pdf

1、最小生成樹(shù)問(wèn)題足一個(gè)經(jīng)典的網(wǎng)絡(luò)優(yōu)化問(wèn)題，目前已有高效的算法在多項(xiàng)式時(shí)間內(nèi)對(duì)其進(jìn)行求解，比如Prim算法與Kruskal算法。然而實(shí)際問(wèn)題往往要求對(duì)生成樹(shù)加上一定的限制，形成了一類(lèi)帶有約束的最小生成樹(shù)問(wèn)題。度約束最小生成樹(shù)問(wèn)題與直徑限制最小生成樹(shù)問(wèn)題就是這類(lèi)問(wèn)題中的兩個(gè)典型代表，并且在現(xiàn)實(shí)生活中具有廣泛的應(yīng)用，例如，通信網(wǎng)絡(luò)，電路設(shè)計(jì)，管道鋪設(shè)等方面。因此，對(duì)這兩種問(wèn)題求解算法的研究具有很好的現(xiàn)實(shí)意義。 本文的主要工作概括如下：

2、 首先，針對(duì)度約束最小生成樹(shù)問(wèn)題，提出了一種新的快速算法。新的快速算法包括兩個(gè)主要部分：第一部分描述如何構(gòu)造一個(gè)度約束樹(shù)：第二部分針對(duì)度約束樹(shù)的構(gòu)造方式設(shè)計(jì)了一種改進(jìn)策略。通過(guò)改進(jìn)策略，獲得了近似程度更高的結(jié)果。文中給出了算法的有效性證明及其復(fù)雜度分析。通過(guò)大量的數(shù)值實(shí)驗(yàn)表明新的快速算法性能良好。 其次，針對(duì)直徑限制的最小生成樹(shù)問(wèn)題，在序列編碼的基礎(chǔ)上設(shè)計(jì)了一種遺傳算法。該算法采用了新的變異算子和局部搜索算子。新的變異算子