English  |  正體中文  |  简体中文  |  Items with full text/Total items : 27533/39387
Visitors : 2541888      Online Users : 34
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search
LoginUploadHelpAboutAdminister

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/17905

Title: 試誤型史坦那樹及單層多組線路連結演算法
On the Heuristic Steiner Tree and Single-Layer Two-Terminal Nets Routing Algorithms for EDA
Authors: Chung-Chih Lou
羅仲志
Contributors: NTOU:Department of Computer Science and Engineering
國立臺灣海洋大學:資訊工程學系
Keywords: 最小生成樹;單層多組線路傳繞演算法;史坦納樹;X架構
minimal spanning tree;single-layer two-terminal nets routing algorithm;Steiner minimal tree;X Architectures
Date: 2003
Issue Date: 2011-07-04
Abstract: X架構上的史坦納樹問題(Steiner tree problem on X Architectures)係指在一個X架構網路上,利用垂直(vertical)、水平(horizontal)以及斜線線段(oblique segments),針對所給定的節點集合Z,將Z中的各個節點以最短的總連接路徑相互連接後所形成的樹。本文中Fan和Jan於先前所提出的方法是透過距離等高線累加的觀念來求出欲連結的各個節點之間的關鍵節點(critical vertex),再重複利用Jan最短路徑演算法中的路徑回溯步驟,最後得到整個的X架構史坦納樹。本文中Lou Steiner tree演算法改進Areibi的觀念,並以Prim最小伸展樹(minimal spanning tree; MST)演算法為基礎,測試自由空間中每一個節點相對於目前Z所形成的MST,測試該點是否有助於降低樹長的能力,然後以貪進法(greedy method)從Improvement Table中選取史坦納節點(Steiner vertex),重複上述步驟進而得到整個史坦納樹的解,且Lou演算法的時間與空間複雜度為O(N2+p3N)以及O(N2),p為Z集合總數,N自由節點總數。 此外,本論文另外以各組線路之特徵排序以及重新排序的機制提出單層多組線路試誤型連結演算法(single-layer two-terminal nets heuristic routing algorithm),得到一個合理的總長度,且其時間複雜度為O(pN)、空間複雜度為O(N),p為欲連結節點的線路數目,N為自由節點的總數。
A Steiner minimal tree for a set Z of vertices on X Architectures is a tree, which interconnects Z using horizontal, vertical and oblique segments of shortest possible total length. In this paper, Lou bases on the Areibi‘s concepts and Prim’s minimal spanning tree algorithm to obtain the heuristic Steiner tree with Steiner ratio of 1.25 on X Architectures. The space and time complexities are O(N2) and O(N2+p3N), respectively, where N and p are the numbers of free and terminal vertices, respectively, p<N. Furthermore, we applies the artributes of two-terminal nets and concept of reordering in the single-layer two-terminal nets routing algorithm to obtain a heuristic solution with reasonable sum of lengths of nets. The space and time complexities are O(N) and O(pN), respectively.
URI: http://ethesys.lib.ntou.edu.tw/cdrfb3/record/#G0M91570015
http://ntour.ntou.edu.tw/ir/handle/987654321/17905
Appears in Collections:[資訊工程學系] 博碩士論文

Files in This Item:

File Description SizeFormat
index.html0KbHTML150View/Open


All items in NTOUR are protected by copyright, with all rights reserved.

 


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback