一些終端斯坦納樹問題之研究; The Terminal Steiner Tree and Related Problems

uTaipei > College of Science > Department of Computer Science > Research Project > Item 987654321/16020

Please use this identifier to cite or link to this item: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16020

Title:	一些終端斯坦納樹問題之研究;The Terminal Steiner Tree and Related Problems
Authors:	陳彥宏
Contributors:	臺北市立教育大學資訊科學系
Keywords:	組合問題;近似演算法;啟發式演算法;NP完備;Max SNP-hard;斯坦納樹問題;終端斯坦納樹問題;選擇內部節點之斯坦納樹問題;選擇內部節點最小生成樹問題;群播繞境;演化樹之重建;大型積體電路繞線;電信通訊
Date:	2012-11-01
Issue Date:	2017-07-31 13:51:35 (UTC+8)
Abstract:	本計畫是探討一些終端斯坦納樹的問題(terminal Steiner tree problems) 及其重新最佳化 (Reoptimization)問題。斯坦納樹問題(Steiner tree problem)是在一個圖上找尋一顆邊長度加總最小的樹連通所有給定的節點。斯坦納樹問題有許多的應用，例如: 群播繞境，演化樹之重建與大型積體電路繞線。給定一個無向完全圖，一個非負數的長度函數在邊上及一個節點集合R，終端斯坦納樹問題 (terminal Steiner tree problem)是去找一顆邊長度加總最小的樹連通R 內所有的節點但每個R 內的節點都要是這棵樹的樹葉。終端斯坦納樹問題可以被廣泛的應用在演化樹之重建，大型積體電路繞線及電信通訊。兩個終端斯坦納樹的變形問題被命名為部份終端斯坦納樹問題(partial terminal Steiner tree problem)及選擇內部節點之斯坦納樹問題(selected-internal Steiner tree problem)。給定一個無向完全圖，一個非負數的長度函數在邊上及二個節點集合R 與R’R，部份終端斯坦納樹問題是去找一個邊上長度加總最小的樹連通R 內所有的節點，但是R’內的節點要是樹葉。另外，選擇內部節點之斯坦納樹問題定義為相同的輸入，其目的卻是去找一個邊上長度加總最小的樹連通R 內的所有節點，但是R’內的節點不能是樹葉（\|R\R’\|2）。這幾個問題都被證明為NP-Complete 及MAX SNP-hard。這幾個問題都有一些近似演算法被設計出。當長度函數是metric 時，終端斯坦納樹問題與部份終端斯坦納樹問題目前最好的近似率約趨近於2.14。選擇內部節點之斯坦納樹問題目前最好的近似率約趨近於2.39。另外是否存在正確的演算法（Exact algorithms）來找尋這些問題的最佳解仍然是未知待解。另外一個議題為這些問題的重新最佳化。給定一個問題的個例(input instance)和一個問題的最佳解，重新最佳化問題為當原個例做一些小改變時，例如:加入一個節點(或邊)或刪除一個節點(或邊)或是改變邊的長度時，如何利用原來的最佳解找到改變後的最佳解或近似解。本計畫首要目標為設計比2.14 倍還小的近似演算法在終端斯坦納樹問題或其兩個變形問題上。我們也預計設計正確演算法來求得問題的最佳解。我們也有興趣討論重新最佳化問題在終端斯坦納樹問題或其兩個變型問題上。
Relation:	研究期間：民10008~10107，國科會計畫編號：NSC100-2221-E133-002
Appears in Collections:	[Department of Computer Science] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	1965	View/Open

Loading...