ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm
文献类型：期刊论文
| 作者 | Hu, Y; Jing, T; Feng, Z; Hong, XL; Hu, XD ; Yan, GY
|
| 刊名 | JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
 |
| 出版日期 | 2006 |
| 卷号 | 21期号:1页码:147-152 |
| 关键词 | rectilinear Steiner minimal tree (RSMT) routing physical design ant colony optimization (ACO) |
| ISSN号 | 1000-9000 |
| 英文摘要 | 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. |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000235342400017 |
| 出版者 | SCIENCE PRESS |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/2605]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Hu, Y |
| 作者单位 | 1.Tsing Hua Univ, Dept Comp Sci & Technol, Beijing 100084, Peoples R China 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China 3.Univ Calif Los Angeles, Dept Elect Engn, Los Angeles, CA 90095 USA |
| 推荐引用方式 GB/T 7714 | Hu, Y,Jing, T,Feng, Z,et al. ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2006,21(1):147-152. |
| APA | Hu, Y,Jing, T,Feng, Z,Hong, XL,Hu, XD,&Yan, GY.(2006).ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,21(1),147-152. |
| MLA | Hu, Y,et al."ACO-Steiner: Ant colony optimization based rectilinear Steiner minimal tree algorithm".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 21.1(2006):147-152. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。