新的分割近似演算法於RST問題之應用

A New Partitioning Algorithm for Solving The RST Problems

吳杰峯(Chieh-Fung Wu)

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2007年)

摘要

矩狀史丹納樹為一個由水平與垂直線所建構之無迴圈網路，此網路跨越所有已知點，矩狀的史丹納樹問題（rectilinear Steiner tree，RST）是一個NP-Complete問題，當RST問題尺度稍大時，計算時間極長，因此有許多學者嘗試推導近似法來求解，以便獲得不錯之行走路徑。L’RST演算法是由學者F.K.Hwang於1976年所提出，在1994年時，Ting-Hai Cha和Yu-Chin Hsu提出Local and Global演算方式來改善L’RST的總長度，然而在節點數過多時其計算時間也明顯變長許多，在本文中主要以Local and Global演算方式為基礎加以延伸提出一個新的演算方法，其方法為先確定節點數目在超過多少時會造成運算時間過長，再利用分割方法來減少個別運算時間且在合併時利用修正方法使得長度之修正，以便減少在節點數過多時所花費之時間。

並列摘要

Rectilinear Steiner tree is an acyclic network constructed by the horizontal and vertical line segment, that span over all the given nodes. RST is an NP-complete problem that consumes tremendous computation time. Due to its complexity on computation, many researchers tried to solve this problem approximately. L’RST algorithm was proposed by F.K.Hwang is 1976. Ting-Hai Cha and Yu-Chin Hsu proposed Local and Global algorithm to improve L’RST method. However, the computation time for Local and Global algorithm increases dramatically when the node number is large. A new algorithm is proposed in this study that divides the node set in to several smaller subsets to reduce the computational complexity , and these subsets will be reunified after the computation. This algorithm gives an efficient way to solve the RST problem with good approximation.

參考文獻

1.M. R. Garey、D. S. Johnson (1977), “The rectilinear Steiner tree problem is np-complete”, SIAM J. Appl. Math., vol. 32, no. 4, pp. 826-834.

2.J. P. Cohoon、D. S. Richards、J. S. Salowe (1990), “An optimal Steiner tree algorithm for a net whose terminals lie on the perimeter of a rectangle”, IEEE Trans. Computer-Aided Design , vol. 9, pp. 398407, Apr.

3.A. V. Aho、M. R. Garey、F. K. Hwang (1977), “Rectilinear Steiner trees: Efficient scecial-case algorithms” , Networks, vol. 7, pp. 37-58.

5.E. Bozorgzadeh、R. Kastner、M. Sarrafzadeh(2003),” Creating and Exploiting Flexibility in Steiner Trees,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp.605-615.

6.C. Chu、Y.-C. Wong(2005),” Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design”, Proc. International Symposium on Physical Design, pp. 28-35.