臺灣博碩士論文加值系統

直線式史坦納樹為一個在平面規劃及繞線中，利用垂直(vertical segments)與水平(horizontal segments)線段以最短路徑連結給定的節點後所形成的樹，同時避免穿越障礙物。在現今積體電路設計中，繞線過程必須考慮各種線路、區塊所產生的障礙物大幅增加此問題之難度，因此良好的策略可縮短線路長度進一步達到繞線節省成本和降低能源耗損之目的。本文中將先計算各節點座標平均值取得關鍵節點(critical vertex)，並以Lee’s演算法[13]洪泛步驟求出關鍵節點與各終端節點(terminal vertices)間之距離，再透過Lee’s演算法中的路徑回溯步驟取得各組終端節點之最短路徑，關鍵節點與終端節點所形成之最短路徑區域重疊部分再設予累加値，並計算各終端節點總累加值再由高至低依序連結。其平均時間複雜度及空間複雜度皆為O(N)，其中N為二維矩陣中網格數目。文獻中以網格圖及Lee’s演算法所發展之史坦納樹演算法中，本演算法之平均時間複雜度及空間複雜度皆為其中最佳，且史坦納樹平均總長度比最佳解稍長7.1%。

Steiner’s Problem is one of the most famous combinatorial-geometrical problems. In fact, Garey et al. [6] has proved that the solution of Steiner’s Problem is at least as difficult as any of the so-called NP-Complete problem. In this paper, a fast maze routing approach to the Steiner tree problems based on the concept of path overlapping in a raster is addressed. The space and average time complexities of the proposed algorithm are both O(N), where N is the number of vertices of the rectilinear plane. Both complexities are the best among the other Maze routing-based algorithms and the average length difference with exact solution is 7.1% in 2-geometry rasters.

謝　辭 Ⅰ
中文論文提要 Ⅱ
英文論文提要 Ⅲ
目　錄 Ⅳ
圖目錄 Ⅵ
表目錄 Ⅶ

第一章　緒　論 1
第一節　研究動機 1
第二節　論文編排方式 1

第二章　文獻回顧與背景簡介 2
第一節　史坦納樹問題之定義及其相關文獻回顧 2
第二節　Lee’s最短路徑連結演算法 4
第三節　Hentschke最短路徑連結演算法 5

第三章　快速迷宮式繞徑史坦納樹演算法 6
第一節　快速迷宮式繞徑史坦納樹演算法之資料結構說明 7
第二節　快速迷宮式繞徑史坦納樹演算法之演算法 8
第三節　快速迷宮式繞徑史坦納樹演算法範例說明 10
第四節　快速迷宮式繞徑史坦納樹演算法之效能分析 12

第四章　演算法模擬執行結果與效能驗證 15
第五章　結論與未來發展 20
參考文獻 21
著作權聲明 23

[1] W. M. Boyce and J. B. Seery, “STEINER 72: An improved version of the minimal network problem,” Tech. Rep., No. 35, Comp. Sci. Res. Ctr. Bell Laboratories, Murray Hill, N.J.
[2] W. M. Boyce, “An improved program for the full Steiner tree problem,” ACMTrans. onMath. Software 3, pp.194-206, 1977.
[3] J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanita, “An improved LP-based approximation for steiner tree,” in ACM Symposiumon Theory of Computing, 2010, pp. 583–592.
[4] C. Chu and Y. C. Wong, FLUTE: Fast lookup tablebased rectilinear Steiner minimal tree algorithm for VLSI design,” IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, ” 27(1):70-83, 2008
[5] E. J. Cockayne and D. G. Schiller, “Computation of Steiner minimal trees in Welsh and Woodall (Eds.)”, Combinatory, Inst. Math. Appl. Pp. 52-71, 1972
[6] L. R. Foulds and R. L. Graham, “TheSteiner problem in phylogeny is NP- Complete,” Adv. Appl. Math., vol. 3, pp. 43-49, 1982.
[7] M. R. Garey, R. L Graham, and D.S. Johnson. The complexity of computing Steiner Minimal Trees. SIAM J. Appl. Math., 32:835-859, 1977.
[8] M. Hanan, “Net wiring for large scale integrated circuits,”IBM Res. Report RC 1375, 1965.
[9] R. F. Hentschke, J. Narasimham, M. O. Johann, and R. L. Reis. “Maze routing Steiner trees with effective critical sink optimization,” In Proceedings of International Symposium on Physical Design, ACM, NY, pp. 135-142, 2007.
[10] Gene Eu Jan, Ki-Yin Chang, Su Gao and Ian Parberry, “A 4-Geometry Maze Router and Its Application on Multi-terminal Nets,”ACM Transactions on Design Automation of Electronic System,” vol. 10, no. 1, pp. 116-135, Jan. 2005.
[11] T. T. Jing, Z. Feng, Y. Hu, Xianlong L. Hong, Xiaodong D. Hu, and G. Y. Yan, “λ-OAT: λ-Geometry Obstacle-Avoiding Tree Construction With O(n log n) Complexity,”IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 26, no. 11, pp. 2073-2079, November 2007.
[12] Tom Tong Jing, Yu Hu, ZheFeng, Xian Long Hong, XiaodongHuc and GuiyingYanc, “A full-scale solution to the rectilinear obstacle-avoiding Steiner problem,” INTEGRATION, the VLSI Journal, 41:413–425, 2008.
[13] C. W. Lin, S. Y. Chen, C. F. Li and Y. W. Chang, “Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs,” IEEE Trans. Computer-Aided Design of Integrated Circuits, 27(4): 643–653, 2008.
[14] R. M. Karp, “Reducibility among combinatorial problems,” in R.E. Miller, J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, pp.85-84, 1972.
[15] C. Y. Lee. “An algorithm for path connection and its applications.” IRE Transaction on Electronic Computers,”EC-10(2): 97-98, 1967.
[16] L. Li and E. F .Y. Young, “Obstacle-avoiding rectilinear Steiner tree construction,” in Proc. Int. Conf. Comput.-Aided Des, 2008, pp. 523–528.
[17] C. H. Lin, Gene Eu Jan, and Yuan-Shin Huang, ”試誤型史坦納樹演算法及電子設計自動化應用PART I: 2D平面中試誤型可容錯八向史坦納樹演算法,” Proceedings of The 2005 National Computer Symposium, Vol. OTD 1-2 No. OT41, Pages 118, Yung-Kang City, Tainan County, Taiwan, R.O.C, December 2005..
[18] C. H. Liu, Y. H. Chou, S. Y. Yuan, and S. Y. Kuo, “Efficient Multilayer Routing Based on Obstacle-Avoiding Preferred Direction Steiner Tree,” in Proc. ISPD, pp. 118–125, 2008.
[19] C. H. Liu, S. Y. Yuan, S. Y. Kuo, and Y. H. Chou, “An O(n log n) Path-Based Obstacle-Avoiding Algorithm for Rectilinear Steiner Tree Construction,” to appear in Proc. DAC, 2009.
[20] C. C. Lou, Y. S. Hwamg, and Gene Eu Jan, “Minimal Steiner Trees in X Architecture with Obstacles,”Proceedings of the 2005 International Conference on VSLI, Las Vegas, Nevada, U. S. A., pp. 198-203, June 2005.
[21] Z. A. Melzak, “On the problem of Steiner,” Canad. Math. Bull., vol. 4, pp. 143-148, 1961.
[22] P. Winter, “An algorithm for the Steiner problem in the Euclidean plane,” Networks, vol. 15, pp. 323-345, 1986.
[23] P. C. Wu, J. R. Gao and T. C. Wang, “A Fast and stable algorithm for obstacle-avoiding rectilinear Steiner minimal tree construction,” 12th Conference on Asia South Pacific Design Automation, 262-267, 2007.