# 臺灣博碩士論文加值系統

(3.236.124.56) 您好！臺灣時間：2021/08/02 07:29

:::

### 詳目顯示

:

• 被引用: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第一章 緒論---------------------------------------------------------------- 11.1 研究背景與動----------------------------------------------------- 11.2 問題描述與名詞定------------------------------------------------ 21.3 研究目的----------------------------------------------------------- 31.4 研究流程----------------------------------------------------------- 3第二章 文獻探討----------------------------------------------------------- 52.1 傳統建構矩形史丹納樹演算法--------------------------------- 52.2 以最小伸展樹為基礎的矩形史丹納樹建構演算法---------- 102.3 The k-Steiner Ratio in the Rectilinear Plane------------------- 182.4 繞線擁擠度-------------------------------------------------------- 22第三章 研究方法----------------------------------------------------------- 263.1 Grid Graph--------------------------------------------------------- 26 3.1.1 演算法步驟-------------------------------------------------------- 283.2 找出候選的史丹納點--------------------------------------------- 283.3 不需考慮的區塊-------------------------------------------------- 303.4 建構整體的最佳RST--------------------------------------------- 373.5 主幹----------------------------------------------------------------- 413.6 合併及修正方法-------------------------------------------------- 433.7 演算法步驟流程-------------------------------------------------- 46第四章 結果討論與分析-------------------------------------------------- 474.1 與L-RST演算法做比較----------------------------------------- 474.2 與Local and Global演算法做比較----------------------------- 514.3 加入矩形障礙物-------------------------------------------------- 544.4 特定的節點圖形-------------------------------------------------- 58第五章 結論與未來展望-------------------------------------------------- 635.1 結論----------------------------------------------------------------- 635.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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 網格網路上RST演算法 2 網格圖上漢米爾頓路徑之決定 3 應用人工智慧技術於預測試管嬰兒治療成功率之研究 4 基於三角幾何學作的圖像辨識 5 豐田生產方式應用於中小企業可行性之研究 6 應用類神經網路與支援向量機於線上即時辨識管制圖非隨機形狀之績效比較 7 應用支援向量機於自相關製程下即時辨識管制圖非隨機形狀之研究 8 應用資料探勘技術於自相關製程中即時偵測管制圖異常形狀之研究 9 非營利組織轉型之研究－以斗南鎮農會為例 10 Floyd-Warshall演算法後簡化禁止路徑的步驟探討 11 應用時間稽延類神經網路即時監控製程數據之研究 12 整合基因演算法與類神經網路於線上辨識管制圖異常形狀之研究 13 評估不確性圓之真圓度 14 新的分割近似演算法於RST問題之應用 15 結合聯合分析法與反應曲面法於綠色環保旅館備品水準之研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室