跳到主要內容

臺灣博碩士論文加值系統

(18.204.56.185) 您好!臺灣時間:2022/08/14 02:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:范啟明
研究生(外文):Kevin C.M. Fan
論文名稱:網狀網路上可容錯之直線式史坦納樹試誤型演算法
論文名稱(外文):Heuristic on Rectilinear Steiner Trees in the Mesh Network with Fault Tolerance
指導教授:詹景裕詹景裕引用關係
指導教授(外文):Gene Eu Jan
學位類別:碩士
校院名稱:國立海洋大學
系所名稱:資訊科學學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:65
中文關鍵詞:容錯積體電路設計多點傳送多處理器排程史坦納樹直線式史坦納樹
外文關鍵詞:level curve accumulationfault toleranceintegrated circuit designmulticastingmultiprocessor schedulingobstacle avoidanceprinted circuit boardrectilinear Steiner tree
相關次數:
  • 被引用被引用: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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top