幾 何 上 最 小 半 徑（直 徑）最 小 成 本 生 成 樹 問 題 之 研 究

Abstract

生成樹(Spanning Tree)是一個最常見的Communication Network Model. 如果一個connected graph G=(V,E)有兩個以上相同成本(Cost)的邊，那麼最小成本生成樹是不唯一的. 當最小成本生成樹不唯一時, 從其中選傳輸延遲(Transmission Delay)最小的即為我們所要的最佳生成樹. 這一類的問題我們稱做最小半徑(直徑)最小成本生成樹問題，且這是歸類在 NP-hard的問題. 我們將介紹一個O(mlogn)的演算法來計算所有最小成本生成樹的聯集和交集，而m =| E | and n =| V |. 而後用一個類似Prim最小生成樹演算法的Heuristic演算法來把所有最小成本生成樹的交集成分連結起來. 這Heuristic演算法所建置出來的生成樹不但滿足最小成本且其半徑(直徑)皆比傳統的Prim演算法小.因為我們用的Heuristic演算法是屬於貪婪(Greedy)的演算法，所以我們在用模擬退火法(Simulated Annealing)來跳脫局部的最小值，去逼近我們所要的最小半徑(直徑)最小成本生成樹.

A spanning tree is a very simple and common communication network model. The minimum (cost) spanning tree (MST) of a connected graph G=(V,E) may not be unique if two or more edges have the same cost. The transmission delay between two nodes in a spanning tree network is measured in terms of its path length. When the minimum cost spanning tree is not unique, the one that minimizes transmission delay is desired. The bicriteria (total cost and transmission delay) optimization problem, the so called minimum radius minimum cost spanning tree or the minimum diameter minimum cost spanning tree problems is known to be NP-hard. An O(m log n) time algorithm is presented for computing the union graph and the intersection graph of all MST’s, where m =| E | and n =| V |. It is shown that the heuristic algorithm based on a locally optimal connection strategy can have an O(n1/3) performance ratio in some cases, where n is the number of points. Experimental results indicate that the heuristic based on a modified Prim’s MST algorithm. MST_H1 outperforms Prim’s MST (minimum spanning tree algorithm) overall and the output of the heuristic can be used as a new oracle MST for other problems. At last, we use simulated annealing to escape local minima based on the output spanning tree of MST_H1.