跳到主要內容

臺灣博碩士論文加值系統

(44.210.83.132) 您好!臺灣時間:2024/05/29 13:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳泓維
研究生(外文):Chen,Hung Wei
論文名稱:迷宮式繞徑史坦納樹快速演算法
論文名稱(外文):A Fast Maze Routing Approach to the Steiner Tree Problems
指導教授:詹景裕詹景裕引用關係
指導教授(外文):Jan, Gene Eu
口試委員:詹景裕宋啟嘉李明哲楊至芳
口試委員(外文):Jan, Gene EuSung, Chi JiaLi, Ming JeYang, Jr Fang
口試日期:2012-07-30
學位類別:碩士
校院名稱:國立臺北大學
系所名稱:電機工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:23
中文關鍵詞:Lee’s演算法史坦納樹最短路徑繞線關鍵節點
外文關鍵詞:Steiner treeNP-Completemaze routingrectilinear plane
相關次數:
  • 被引用被引用:1
  • 點閱點閱:689
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
直線式史坦納樹為一個在平面規劃及繞線中,利用垂直(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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top