李德財臺灣大學:資訊工程學研究所鐘健元Chung, Chien-YuenChien-YuenChung2010-06-022018-07-052010-06-022018-07-052008U0001-0402200816081300http://ntur.lib.ntu.edu.tw//handle/246246/184913在此論文中，我們將討論最小直徑最小成本生成樹的問題，最小直徑最小成本生成樹就是在所有的最小生成樹當中去找到直徑最小的。這個圖論版本的問題在1991年被證明是NP-hard[5]。而計算幾何的版本也在隨後被證明是NP-hard[1]。我們將會對於在平面上給定一個點集合去計算幾何的最小直徑最小成本生成樹這個問題給兩種類型的經驗法則演算法。一種是從最小成本生成樹的觀點，另一種則是從最小直徑生成樹。們已經把以上的演算法實作在平台Algorithm Benchmark System (ABS) of openCPS web portal，http://www.opencps.org [2]上面，我們也將會有詳細的分析敘述。據這個測試系統我們給定以最小直徑生成樹為觀點的演算法是能夠比以最小成本生成樹為觀點的計算出比較好的結果，但是相對的最小直徑生成樹為觀點的演算法的時間複雜度就高出了許多。In this thesis, we consider a bicriteria problem, called minimum diameter minimum cost spanning tree (MDMCST) problem, which is to construct a minimum diameter spanning tree (MDST) among all possible minimum cost spanning trees (MST). The graph-theoretic version of this bicriteria problem has been known to be NP-hard since 1991[5]. The geometric version, however, was shown to be NP-hard much later[1]. We present two kinds of heuristic algorithms for the geometric minimum diameter and minimum cost spanning tree (GMDMCST) problem for a set of points in the plane, from the viewpoint of the MST, called MST-based heuristic algorithms, and from the viewpoint of the MDST, called MDST-based heuristic algorithms, respectively.e have implemented them using the Algorithm Benchmark System (ABS) of openCPS web portal, http://www.opencps.org [2] and performed a detailed analysis of both heuristics.n the experimental results of this benchmark system, we find that the result of MDST-based heuristic algorithms is better than the result of MST-based heuristic algorithms, but the time complexity of MDST-based heuristic algorithms is worse than MST-based heuristic algorithms.口試委員會審定書…………………………………………………… i謝………………………………………………………………….…. ii文摘要…………………………………………………………….… iii文摘要………………………………………………………………. iv一章 Introduction………………………………………………….. 1一節The Basic Definition………….…………………………… 4二章 The MST-based Heuristic………………………………….. 13一節Prim-like Heuristic…………...…….…………………..… 13二節Kruskal-like Heuristic…………...…………………..…… 21三章 The MDST-based Heuristic………………………………… 26一節K-center Heuristic……………….……………….………. 26四章 The Algorithm Benchmark System (ABS) of www.opencps.org35五章 Conclusions…………………………..…………………….. 39amp;#63851;考文獻……………………………………………………………… 41application/pdf692952 bytesapplication/pdfen-US最小生成樹最小半徑生成樹minimum spanning treeminimum diameter spanning treeminimum diameter minimum cost spanning treethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/184913/1/ntu-97-R94922098-1.pdf