約束最小生成樹算法的研究.pdf

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

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