雙參數最佳生成樹之研究

Abstract

我們在這篇論文中研究了三個最佳化雙參數生成樹(Optimum Two- Parameter Objective Spanning Tree)的課題。雙參數生成樹是一個相當 複雜的問題，然而因為它在圖形學(Graph Theory)、演算法(Algorithms) 及運輸與通訊網路(Transportation and Communication Networks)等領 域都有應用，使得這些題目深具研究價值。首先，我們研究了雙參數生成 樹的組件變動演算問題(Element Perturbation Problem)。當一個圖形的 連線組件(Edge)在某些情況下失效或斷線，將會使這個圖形(Graph)的最 佳化生成樹有巨大的改變。我們基於Hassin與Tamir的演算法，研究出了 最佳的雙參數生成樹的組件變動演算法。同時，我們也可找到此圖形的次 佳生成樹 (Second Optimal Solutions)與關鍵組件(Critical Elements) 。其次，我們將原有的最低之成本與可靠度比例生成樹(Minimum Cost / Reliability Ratio Spanning Tree)問題的演算法改進，使得演算複雜 度 (Computational Complexity)由連線組件數目的四次方降到三次方。 這個演算法對於架構成本低而可靠度又高的運輸或通訊網路規劃極具助益 。最後，我們設計了一個實用的最佳生成樹基因演算法。基因演算法 (Genetic Algorithms)曾被廣泛地應用在各種演算問題上，而今才初次由 我們用來解決圖形網路中的生成樹問題，應用基因演算法不能保證找到最 佳的解答，但是它適用性高，不論問題限制 (Constraints)多麼複雜，它 都能找到接近最佳的解答。我們對這種生成樹基因演算法做的實驗，頗能 附合我們的規劃，並提供了一些結果做基因演算法的應用參考。 In this dissertation, we discuss three research topics on Optimum Two-Parameter Spanning Trees. Although being complex, these problems have applications on Graphs, Algorithms, Network researches. First, we study the Element Perturbation Problem. Based on Hassin and Tamir's algorithm, we find optimum algorithm to compute optimum two-parameter spanning trees of a graph when one of the edge in the graph is removed. We also find second optimal solutions and critical elements of the graph. Second, we improve the time complexity of the algorithm to compute the Minimum Cost / Reliability Ratio spanning trees of a graph. Third, we design a genetic algorithm to find sub- optimal spanning trees of a graph. Experiments on the robust algorithm are presented in this dissertation.