【摘 要】
：
The rectilinear Steiner minimal tree (RSMT) problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-comple
【机 构】
：
Department of Computer Science and Technology,Electrical Engineering Deparment,Institute of Applied
【基金项目】
：
the National Natural Science Foundation of China (NSFC) under;the Specialized Research Fund for the Doctoral Program of Higher Education (SRFDP) of China under
论文部分内容阅读
The rectilinear Steiner minimal tree (RSMT) problem is one of the fundamental problems in physical design, especially in routing, which is known to be NP-complete. This paper presents an algorithm, called ACO-Steiner, for RSMT construction based on ant colony optimization (ACO). An RSMT is constructed with ants movements in Hanan grid, and then the constraint of Hanan grid is broken to accelerate ants movements to improve the performance of the algorithm. This algorithm has been implemented on a Sun workstation with Unix operating system and the results have been compared with the fastest exact RSMT algorithm, GeoSteiner 3.1 and a recent heuristic using batched greedy triple construction (BGTC).Experimental results show that ACO-Steiner can get a short running time and keep the high performance. Furthermore, it is also found that the ACO-Steiner can be easily extended to be used to some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in global routing.
其他文献
目的 了解上海市宝山区孕妇梅毒流行特征、防治现状,为制订防治措施提供依据.方法 对上海市宝山区2004至2009年的孕妇梅毒监测资料进行回顾性分析.结果 孕妇梅毒筛查阳性率0
多囊卵巢综合征(PCOS)是青春期和育龄妇女常见的一种主要累及生殖系统的慢性内分泌疾病.其发病机制涉及遗传、胰岛素抵抗、饮食、环境及精神心理等多种因素.其临床表现多变,
静脉留置针已在临床广泛使用,它可减少患者的穿刺次数,减轻患者痛苦,方便临床用药,得到广大患者的青睐.但在使用中静脉炎的发生不仅给患者带来痛苦,还会延长患者的住院天数,
骨关节炎是一种退行性病损,表现为关节软骨的破坏和软骨下骨的吸收或异常增生,细胞因子通过各种机制调节该过程中软骨细胞的活动.本文就相关细胞因子在骨关节炎软骨病变过程
结合《中国急性缺血性脑卒中诊治指南2010》介绍缺血性脑卒中(ischemic stroke,IS)和短暂性脑缺血发作(transient ischemic attack,TIA)的急性期治疗,包括抗栓治疗(溶栓、抗
目的 比较改良内窥镜微创切开腕管减压与传统切开法治疗腕管综合征的术后疗效.方法 将70例单侧发病的腕管综合征患者随机分为改良内窥镜微创切开腕管减压(改良微创治疗组)与
目的 探讨正常肾脏3.0T磁共振扩散加权成像的影像表现,为合理选择b值及测量平面提供依据.并探讨性别和年龄等因素对正常值的影响.方法 对48例健康志愿者行DWI扫描,b值取100、
[目的]探讨成人社区获得性支原体肺炎（CAP）的临床特点.[方法]回顾性分析2008年1月至2011年1月本院确诊的CAP 患者92例的临床资料.[结果]CAP最常见症状有发热、顽固性咳嗽,有皮
目的 观察联合应用氟哌噻吨美利曲辛和地衣芽孢杆菌活菌治疗腹泻型肠易激综合征的临床疗效.方法 将临床诊断为腹泻型肠易激综合征的186例患者按随机数字表法分为观察组(地衣
A simple and efficient method for cloning the flanking genomic sequences of a known DNA region is reported in this study. This method combined partial restricti