在分群斯坦納樹與相關問題的實作研究

An Experimental Study on Clustered Steiner Tree and Related Problems

余柏頡(Po-Chieh Yu)

指導教授 ： 吳邦一

國立中正大學/工學院/資訊工程學系/碩士(2014年)

摘要

在這篇論文裡，我們主要對兩個問題做研究，分別是，Clustered Steiner tree problem (called CluSteiner)還有minimum routing cost terminal tree problem(MRCTT)。CluSteiner問題是Steiner minimum tree的一個變形，這問題的instance是給一個metric graph還有一個required vertex set的partition，可以看作把required vertices分群。Metric graph是一個完全圖，且邊上的cost都是非負的，在這圖上找任一三角形都滿足三角不等式。如果有一個Steiner tree連到某一群裡所有的required vertices，而這Steiner tree的最小子樹稱作local tree。Clustered Steiner tree是連到所有的required vertices，而且其中每個群的local tree互相不相交。如果我們要求找一個Clustered Steiner tree而其邊上所有邊加總起來最少，那這問題是NP-hard。所以我們對CluSteiner問題提出了四個啟發示演算法，在我們的實驗結果裡可以看到，我們演算法給的結果是可接受的答案。

第二個問題，MRCTT問題是optimal product-requirement communication spanning tree(PROCT)問題的變形。PROCT問題是NP-hard，所以MRCTT問題也是NP-hard。我們對MRCTT問題實作一個exact algorithm，這exact algorithm是使用branch-and-bound方法來實作的。由我們實驗的結果可以看到我們的lower bound還有branch rule是有效的。

並列摘要

無資料

並列關鍵字

minimum routing cost terminal tree ； heuristic algorithm ； clustered steiner minimum tree ； branch and bound

參考文獻

[1] Du, D. Z., Zhang, Y., & Feng, Q. (1991, October). On better heuristic

for Euclidean Steiner minimum trees. In FOCS (Vol. 91, pp. 431-439).

[2] Du, D. Z. (1995). On component-size bounded Steiner trees. Discrete

Applied Mathematics, 60(1), 131-140.

& Control, 11(11).