迷宮式繞徑史坦納樹快速演算法

直線式史坦納樹為一個在平面規劃及繞線中，利用垂直(vertical segments)與水平(horizontal segments)線段以最短路徑連結給定的節點後所形成的樹，同時避免穿越障礙物。在現今積體電路設計中，繞線過程必須考慮各種線路、區塊所產生的障礙物大幅增加此問題之難度，因此良好的策略可縮短線路長度進一步達到繞線節省成本和降低能源耗損之目的。本文中將先計算各節點座標平均值取得關鍵節點(critical vertex)，並以Lee’s演算法[13]洪泛步驟求出關鍵節點與各終端節點(terminal vertices)間之距離，再透過Lee’s演算法中的路徑回溯步驟取得各組終端節點之最短路徑，關鍵節點與終端節點所形成之最短路徑區域重疊部分再設予累加値，並計算各終端節點總累加值再由高至低依序連結。其平均時間複雜度及空間複雜度皆為O(N)，其中N為二維矩陣中網格數目。文獻中以網格圖及Lee’s演算法所發展之史坦納樹演算法中，本演算法之平均時間複雜度及空間複雜度皆為其中最佳，且史坦納樹平均總長度比最佳解稍長7.1%。

關鍵字

Lee`s演算法；史坦納樹；最短路徑；繞線；關鍵節點

並列摘要

Steiner’s Problem is one of the most famous combinatorial-geometrical problems. In fact, Garey et al. [6] has proved that the solution of Steiner’s Problem is at least as difficult as any of the so-called NP-Complete problem. In this paper, a fast maze routing approach to the Steiner tree problems based on the concept of path overlapping in a raster is addressed. The space and average time complexities of the proposed algorithm are both O(N), where N is the number of vertices of the rectilinear plane. Both complexities are the best among the other Maze routing-based algorithms and the average length difference with exact solution is 7.1% in 2-geometry rasters.

並列關鍵字

Steiner tree ； NP-Complete ； maze routing ； rectilinear plane

參考文獻

[2] W. M. Boyce, “An improved program for the full Steiner tree problem,” ACMTrans. onMath. Software 3, pp.194-206, 1977.

[4] C. Chu and Y. C. Wong, FLUTE: Fast lookup tablebased rectilinear Steiner minimal tree algorithm for VLSI design,” IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, ” 27(1):70-83, 2008

[6] L. R. Foulds and R. L. Graham, “TheSteiner problem in phylogeny is NP- Complete,” Adv. Appl. Math., vol. 3, pp. 43-49, 1982.

[7] M. R. Garey, R. L Graham, and D.S. Johnson. The complexity of computing Steiner Minimal Trees. SIAM J. Appl. Math., 32:835-859, 1977.

[9] R. F. Hentschke, J. Narasimham, M. O. Johann, and R. L. Reis. “Maze routing Steiner trees with effective critical sink optimization,” In Proceedings of International Symposium on Physical Design, ACM, NY, pp. 135-142, 2007.

國際替代計量

迷宮式繞徑史坦納樹快速演算法

未授權

主題瀏覽