QQ客服 官方微博 反馈留言

	考虑障碍的多端点最小直角Steiner树构造算法
	杨旸 ; 经彤 ; 洪先龙 ; 朱祺 ; 王垠 ; Yang Yang ; Jing Tong ; Hong Xianlong ; Zhu Qi ; Wang Yin
	2010-06-09 ; 2010-06-09
关键词	布线 最小直角Steiner树 障碍 多端点线网 routing rectilinear Steiner minimal tree (RSMT) obstacles multi-terminal TP311.12
其他题名	An Efficient 2-Step Heuristics for Rectilinear Steiner Minimal Tree Construction among Obstacles
中文摘要	首先将所有障碍视为不存在 ,构造初始Steiner树、连接线网所有端点 ,可采用已有的无障碍Steiner树算法来实现 然后考虑障碍的影响 ,改造所构造的初始Steiner树 :找到初始Steiner树与障碍的相交点 ,重布某些树边 ,使它们绕过障碍 ,并尽量保持树长较短 ;进一步地 ,加入预处理和后期处理措施 ,以更好地处理特殊线网并使算法的结果更优 该算法能够处理多个障碍的情况 ,并能适应多种形状的障碍 ;同时 ,算法有较高的效率 ,其复杂度为O(mn) ,其中 ,m和n分别是障碍个数和线网端点数 该算法已经在SUN工作站、Unix上利用C语言编程实现 ,并进行了MCNC电路测试 测试结果表明 :文中算法得到的树长结果仅与最优值平均相差 5. 31% ,且算法的执行时间保持在 1s以内; A primary tree is first constructed without considering obstacles. Intersections of the primary tree edges with obstacles are found out and relevant parts of the primary tree are reconnected to keep clear of obstacles while the total length of the tree being shortest. Moreover, a preprocessing and post-processing are added into the second step to tackle some special treatments and improve the solution quality. The heuristics can deal with multi-obstacle and obstacles of diversified shapes with O(mn) complexity, where m is the number of obstacles and n is the number of terminals. Experimental tests on MCNC benchmarks show that the algorithm can get good results on wire length, its average redundancy compared with minimal trees is 5.31% and the runtime for all cases is within 1 second.; 国家自然科学基金(60373012); 国家“八六三”高技术研究发展计划(2002AA1Z1460); 高校博士点基金(20020003008); 清华大学骨干人才支持计划([2002]4)
语种	中文 ; 中文
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/56066]
专题	清华大学
推荐引用方式 GB/T 7714	杨旸,经彤,洪先龙,等. 考虑障碍的多端点最小直角Steiner树构造算法[J],2010, 2010.
APA	杨旸.,经彤.,洪先龙.,朱祺.,王垠.,...&Wang Yin.(2010).考虑障碍的多端点最小直角Steiner树构造算法..
MLA	杨旸,et al."考虑障碍的多端点最小直角Steiner树构造算法".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。