跳到主要內容

臺灣博碩士論文加值系統

(3.236.124.56) 您好!臺灣時間:2021/08/02 07:29
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:周逸達
研究生(外文):Yi-Da Chou
論文名稱:箱型圖演算法於RST問題之研究
論文名稱(外文):A Study of Box-diagram Construction for the Rectilinear Steiner Tree Problem
指導教授:黃俊平黃俊平引用關係
指導教授(外文):Jyun ping Huang
學位類別:碩士
校院名稱:國立虎尾科技大學
系所名稱:工業工程與管理研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:60
中文關鍵詞:矩狀的史丹納樹NP-Complete格子圖最小展開樹box圖
外文關鍵詞:Rectilinear Steiner TreeNP-CompleteBox-diagramminimum spanning treeGrid Graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:282
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
矩狀的史丹納樹( rectilinear steiner tree,RST )問題,是求在一平面上指定的點與點間以水平及垂直線所建構成的無迴圈網路,此問題為NP-Complete問題,當節點數增大時,計算時間呈指數型態增加,因此有許多學者嘗試近似法求解,以便求得不錯的路徑解 。
直接求解RST問題的演算過程相當複雜,因而衍生出將連接節點的路徑投射在格子圖(grid graph)上,以格子圖上的水平垂直線段交點與問題本身的節點來建構RST的圖形,本研究是將實際平面的RST問題轉化到格子圖上,試圖在格子圖上探討RST最佳解的圖形。
本研究的方法有別於以往學者所先建構最小展開樹法(minimum spanning tree,MST),是在格子圖上以逐一節點對其鄰近兩點建構起box圖,再次縮小了投射在格子圖的區域,接著找出候選的史丹納點連起主幹做為出發建構RST解的基礎,最後再利用區域與整體的修正方法使得總長度縮短,更優化其解,此外本研究針對平面上一般與含有障礙物RST問題來進行模擬,並都可獲得逼近最佳解的RST。
The rectilinear steiner tree(RST) problem is to construct a graph of a given set of points on the plane and the graph containing only horizontal and vertical line segments in a network that has no loop. This problem has been shown to be NP-complete that means the computation time increases exponentialy as nodes increase. Thus, researchers have proposed many heuristic algorithms to achieve a good solution.
The calculation of RST is a complicated problem that many researchers tried to solve this problem in different way. We construct the graphs of RST with nodes on the grid graph. This study is to transform RST problem of the actual plane into the grid graph to approach the optimal solution of RST.
The proposed algorithm is different from the algorithms of constructing minimum spanning tree(MST) to solve RST problem,The initial step of the algorithm is to construct the Box-diagram of each node and its two nearest nodes one by one. It again narrows the projection region on the grid graph. Then the algorithm finds out the trunk connected with candidate Steiner points as the basis to construct solution. Finally, using more local and global refinement to reduce the total length. In addition, this study focuss on the RST problem containing obstacles to obtain the quasi optimal solution of RST.
中文摘要 ----------------------------------------------------------------------- i
英文摘要 ----------------------------------------------------------------------- ii
誌謝 ----------------------------------------------------------------------- iii
目錄 ----------------------------------------------------------------------- iv
表目錄 ----------------------------------------------------------------------- vi
圖目錄 ---------------------------------------------------------------------- vii
第一章 緒論---------------------------------------------------------------- 1
1.1 研究背景與動----------------------------------------------------- 1
1.2 問題描述與名詞定------------------------------------------------ 2
1.3 研究目的----------------------------------------------------------- 3
1.4 研究流程----------------------------------------------------------- 3
第二章 文獻探討----------------------------------------------------------- 5
2.1 傳統建構矩形史丹納樹演算法--------------------------------- 5
2.2 以最小伸展樹為基礎的矩形史丹納樹建構演算法---------- 10
2.3 The k-Steiner Ratio in the Rectilinear Plane------------------- 18
2.4 繞線擁擠度-------------------------------------------------------- 22
第三章 研究方法----------------------------------------------------------- 26
3.1 Grid Graph--------------------------------------------------------- 26
3.1.1 演算法步驟-------------------------------------------------------- 28
3.2 找出候選的史丹納點--------------------------------------------- 28
3.3 不需考慮的區塊-------------------------------------------------- 30
3.4 建構整體的最佳RST--------------------------------------------- 37
3.5 主幹----------------------------------------------------------------- 41
3.6 合併及修正方法-------------------------------------------------- 43
3.7 演算法步驟流程-------------------------------------------------- 46
第四章 結果討論與分析-------------------------------------------------- 47
4.1 與L-RST演算法做比較----------------------------------------- 47
4.2 與Local and Global演算法做比較----------------------------- 51
4.3 加入矩形障礙物-------------------------------------------------- 54
4.4 特定的節點圖形-------------------------------------------------- 58
第五章 結論與未來展望-------------------------------------------------- 63
5.1 結論----------------------------------------------------------------- 63
5.2 未來展望----------------------------------------------------------- 63
參考文獻 ----------------------------------------------------------------------- 64
1.Aho, A. V., Garey, M. R., Hwang, F. K. (1977), “Rectilinear Steiner trees: Efficient special-case algorithm”, Networks, vol. 7, pp.37-58.
2.Bozorgzadeh, E., Kastner, R., Sarrafzadeh, M. (2003), “Creating and Exploiting Flexibility in Steiner Trees”, IEEE, pp.605-615.
3.Berman, P., Ramaiyer, V. (1994), “ Improved approximation algorithms for the Steiner tree problem”, J. Algorithms, vol. 17, pp.381-408.
4.Borchers, Al., Du, Ding. Zhu. (1997), “The k-Steiner ratio in graphs”, SIAM J. Comput, vol. 26, pp.857-869.
5.Chao, Ting. Hai., Hsu, Yu. Chin. (1990), “Rectilinear Steiner Tree Construction By Local and Global Refinement”, IEEE, pp.303-309.
6.Cohoon, J. P., Richards, D. S., Salowe, J. S. (1990), “An optimal Steiner tree algorithm for a net whose terminals lie on the perimeter of a rectangle”, IEEE, vol. 9, pp.398-407.
7.Chan, H., Qiao, C., Zhou, F., Cheng, C. K. (2002), “Refine single trunk tree:a rectilinear Steiner tree generator for interconnect prediction”, Internation-al Workshop on System-Level Interconnect Prediction, pp. 85-89.
8.Chu, C., Wong, Y. C. (2005), “Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI for Design”, Proc. International Symposium on Physical Design, pp.28-35.
9.Chen, H. M., Zhou, H., Young, F. Y., Wong, D. F. (1999), “Integrated Floorplanningand Interconnect Planning”, Proc. IEEE International Conference on Computer Aided Design, pp.354-357.
10.Du, D. Z., Zhang, Y. J., Feng, Q. (1991), “On better heuristic for Euclidean Steiner minimum trees”, Proceedings of the 32nd Annual Symposium on the Foundations of Computer Science, pp.431-439.
11.Garey, M. R., Johnson, D. S. (1977), “The rectilinear Steiner tree problem in NP-complete”, SIAM J. Appl. Math, vol. 32(4), pp.826-834.
12.Ho, J. M., Vijayan, G ., Wong, C. K. (1989), “A new approach to the rectilinear Steiner tree problem”, Proc. 26th ACM/IEEE Design Automation Conf, pp.161-166, June.
13.Hwang, F. K. (1976), “On Steiner minimal trees with rectilinear distance”, SIAM J. Appl. Math, vol. 30(1), pp.104-114.
14.Hwang, F. K. (1979), “An O ( n log n ) algorithm for suboptimal rectilinear Steiner trees”, IEEE Trans. Circuits Syst , vol. CAS-26, pp. 75-77, January.
15.Hanan, M. (1966), “On Steiner’s problem with rectilinear distance”, SIAM J. Appl. Math., vol. 14(2), pp.255-265.
16.Ho, J. M., Vijayan, G., Wong, C. K. (1990), “New Algorithms for the Rectilinear Steiner Tree Problem”, IEEE Tramaction on Computer-Aided Design, vol. 9(2), pp.161-166, February.
17.Kahng, A.B., Robins, G. (1992), “A New Class of Iterative Steiner Tree Heuristics With Good Performance”, IEEE, pp.893-902.
18.Lee, J. H., Bose, N. K., Hwang, F. K. (1976), “Use of Steiner’s problem in suboptimal routing in rectilinear metric”, IEEE Trans. Circuits Syst, vol. CAS-23, pp.470-476, July.
19.Lengauer, T. (1990), “Combinatorial Algorithms for Integrated Circuit Layout”, John Wiley & Sons.
20.Wang, M., Sarrafzadeh, M. (2000), “Modeling and Minimization of RoutingCongestion”, Proc.ACM/SIGDA Asia and South Pacific Design Automation Conference, pp.185-190.
21. Zelikovsky, A. Z. (1993), “An 11/6-approximation algorithm for the network Steiner problem”, Algorithmica 9, 463-470.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top