臺灣博碩士論文加值系統

直線式史坦納樹(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.