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

(18.204.56.185) 您好！臺灣時間：2022/08/14 02:53

:::

### 詳目顯示

:

• 被引用:2
• 點閱:156
• 評分:
• 下載:0
• 書目收藏:0
 直線式史坦納樹(rectilinear Steiner tree; RSP)係指於一網格狀平面上，僅利用垂直線段(vertical segment)與水平線段(horizontal segment)，針對所給定的節點集合Z，將Z中的各個節點以最短的總連接路徑相互連接後所形成的樹。其與最小伸展樹(minimal spanning tree; MST)不同之處在於最小伸展樹僅允許由節點連接至節點的路徑型態，而直線式史坦納樹尚可允許由節點連結至一現存路徑上的某一點。直線式史坦納樹可應用於印刷電路版的電路連接、積體電路路由設計、多點傳送網路路徑的規劃、二維儲存設備排程以及多處理器的排程上。針對直線式史坦納樹的問題，許多相關的演算法，包含了確切型演算法(exact algorithm)、試誤型演算法(heuristic algorithm)以及遺傳演算法(genetic algorithm)等已被提出。然而，大部份的演算法均僅能於無障礙物的網格平面上找出直線式史坦納樹，此於實際的應用上是不實用的。本文將提出一個適用於具有壞節點(faulty nodes)的網狀網路(mesh network)上找出直線式史坦納樹的試誤型演算法。其先將利用Lee的連結演算法來求取出任意指定兩點之間的最短路徑。再透過距離等高線累加的觀念來求出欲連結的各個節點之間的關鍵節點(critical vertex)；最後，再利用Lee 演算法中的路徑回溯過程取得直線式史坦納樹。本計劃欲提出的試誤型演算法其空間複雜度為O(p N)，而其時間複雜度為O(p 2N)，其中p為Z 中的節點總數，而N 則為給定網狀網路上的所有節點數。此外，為驗証本計劃所提出之試誤型演算法，本計劃亦將提出一針對具障礙物的網格空間上之確切型直線式史坦納樹演算法。
 A minimal rectilinear Steiner tree for a set Z of vertices in the plane is a tree, which interconnects Z using horizontal and vertical lines of shortest possible total length. Such trees have potential application to wire layout for printed circuit boards, integrated circuit design, network design for multicast routing, two dimensional disk scheduling, and multiprocessor scheduling. At present many exact, heuristic, and genetic algorithms have been shown for constructing these trees in general. However, most of these algorithms, except the switchbox routing ones, solve the rectilinear Steiner tree in a plane without faulty vertices, which is not practical in general cases. In this thesis, a heuristic solving rectilinear Steiner tree problem with fault tolerance is presented. Lee’s connection algorithm is applied to obtain the shortest path between any two arbitrary vertices in a mesh with faulty vertices, and a level curve accumulation scheme in terms of distance will also be utilized to obtain the critical vertex in global. The space and time complexities of the heuristic proposed are O(pN) and O(p 2N), respectively, where p is the total number of vertices in Z, and N is the number of vertices in the given mesh. An exact algorithm will also be presented to compare the heuristic simulation.
 摘要 1 Abstract 3 目錄 4 圖目錄 5 表目錄 7 第一章 緒論 8 第二章 文獻回顧與背景介紹 10 第三章 可容錯之直線式史坦納樹試誤型演算法 17 第四章 可容錯之直線式史坦納樹確切型演算法 37 第五章 演算法模擬執行結果與效能驗證 45 第六章 結論與未來發展 60 參考文獻 62
 [1] A. V. Aho, M. R. Garey, and F. K. Hwang, “Rectilinear Steiner trees: efficient special case algorithms,” Networks, vol. 7, pp. 37-58, 1977.[2] W. M. Boyce, “An improved program for the full Steiner tree problem,” ACM Trans. on Math. Software 3, pp. 194-206, 1977.[3] 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.[4] S. K. Chang, “The generation of minimal trees with a Steiner topology,” J. ACM, vol. 19, pp. 669-711, 1972.[5] E. J. Cockayne and D. G. Schiller, “Computation of Steiner minimal trees in Welsh and Woddall (Eds.), Combinatorics, Inst. Math. Appl. pp. 52-71, 1972.[6] L. R. Foulds and R. L. Graham, “The Steiner problem in phylogeny is NP-complete,” Adv. Appl. Math., vol. 3, pp. 43-49, 1982.[7] M. R. Garey and D. S. Johnson, “The rectilinear Steiner problem is NP-complete,” J. SIAM Appl. Math., vol. 32, pp. 826-834, 1977.[8] M. Hanan, “Net wiring for large scale integrated circuits,” IBM Res. Report RC 1375, 1965.[9] M. Hanan, “On Steiner’s problem with rectilinear distance,” J. SIAM Appl. Math., vol. 14, pp. 255-265, 1966.[10] J. Hesser, R. Manner, and O. Stucky, “Optimization of Steiner trees using genetic algorithms,” Proc. 3rd Int. Conf. Genetic Algorithms, pp. 231-236, 1989.[11] Jan-Ming Ho, Copalakrishnan Vijayan, and C. K. Wong, “New algorithms for the rectilinear Steiner tree problem,” IEEE Trans. Computer-aided Design, vol. 9, pp. 185-193, 1990.[12] F. K. Hwang, “On Steiner minimal trees with rectilinear distance,” SIAM J. Appl. Math., vol. 30, pp. 104-114, 1978.[13] F. K. Hwang, “ An O(n log n) algorithm for suboptimal rectilinear Steiner trees,” IEEE Trans. Circuits and Systems, CAS-26, pp. 75-77, 1979.[14] Gene Eu Jan and Ki-Ying Chang, “An O(N) Shortest Path Algorithm on Raster,” Technical Report CS01001, Department of Computer Science, National Taiwan Ocean University, Taiwan, Jul. 2001.[15] Gene Eu Jan, Ki-Ying Chang and Jhiann Shing Wu, “The Planning of a Shortest Path in the 3D Raster,” Technical Report CS01002, Department of Computer Science, National Taiwan Ocean University, Taiwan, Jul. 2001.[16] Gene Eu Jan, Ming-Bo Lin and Yung-Yuan Chen, “Computerized Shortest Path Searching for Vessels,” Journal of Marine Science and Technology, Vol. 5, No. 1, 1997, pp. 95-99.[17] B. A. Julstrom, “A genetic algorithm for the rectilinear Steiner problem,” Proc. 5th Int. Conf. Genetic Algorithms, pp. 474-480, 1993.[18] A. Kapsalis, V. J. Rayward-Smith, and G. D. Smith, “Solving the graphical Steiner tree problem using genetic algorithms,” Journal of the Operational Research Society, vol. 44, no. 4, pp. 397-406, 1993.[19] 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.[20] P. Korhonen, “An algorithm for transforming a spanning tree into a Steiner tree,” Proc. 9th Int. Math. Progr. Symp., Budapest 1976. North-Holland, Amsterdam, pp. 349-357, 1979.[21] C. Y. Lee, “An algorithm for path connections and its applications,” IRE Trans. Electron. Computer, vol. EC-10, pp. 346-365, Sept. 1961.[22] J. H. Lee, N. K. Bose, and F. K. Hwang, “ Use of Steiner’s problem in suboptimal routing in rectilinear metric,” IEEE Trans. Circuit and Systems, CAS-23, pp. 470-476, 1976.[23] Z. A. Melzak, “On the problem of Steiner,” Canad. Math. Bull., vol. 4, pp. 143-148, 1961.[24] R. C. Prim, “Shortest connection networks and some generalizations, Bell System Tech. J., vol. 36, pp. 1389-1401, 1957.[25] J. M. Smith, “An O(n log n) heuristic for Steiner minimal tree problems on the Euclidean metric,” Networks, vol. 11, pp. 23-39, 1981.[26] J. M. Smith, D. T. Lee, and J. S. Liebman, “An O(n log n) heuristic algorithm for the rectilinear Steiner minimal tree problem,” Eng. Optimization, vol. 4, pp.179-192, 1980.[27] J. M. Smith and J. S. Liebman, “Steiner trees, Steiner circuits and the interference problem in building design,” Eng. Optimization, vol. 4, pp. 15-36, 1979.[28] P. Winter, “An algorithm for the Steiner problem in the Euclidean plane,” Networks, vol. 15, pp. 323-345, 1985.[29] P. Winter, “ Steiner problem in networks: a survey,” Networks, vol. 17, pp. 129-167, 1987.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 試誤型史坦那樹及單層多組線路連結演算法 2 試誤型史坦那樹演算法及電子設計自動化的應用 3 全光多波長分工光纖網路之架構設計與協定分析

 無相關期刊

 1 試誤型史坦那樹及單層多組線路連結演算法 2 二維格狀運輸網路中具有轉彎加權之最佳路徑規劃 3 三度空間與二次曲面之最短路徑規劃及動態追截 4 一種應用於車速自動偵測之適應性比對演算法 5 矩形容器內流體振盪控制之研究 6 分散式系統於可程式控制器之應用 7 利用應力波有限元素法探討格架結構音之傳播 8 遺傳演算法於零工式生產排程系統之應用 9 端肘板鍵槽對連續艙口圍緣角隅強度之影響 10 鍵槽對艙口角隅應力集中現象改善之結構分析 11 質點影像測速法於薄膜流場的量測應用 12 應用平行化基因演算法改進螺槳幾何之設計 13 車輛－軌道耦合系統之動態分析 14 線性時間之田字型可避障最短路徑連結 15 智慧型越獄路線規劃

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