| |
| he 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). We construct a RSMT with ants’ movements in Hanan grid, and then we break the constraint of Hanan grid 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, Geo-Steiner 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, we also find that our ACO-Steiner is easily extended to be used into some other problems, such as rectilinear Steiner minimal tree avoiding obstacles, and congestion reduction in g |
|
| Keywords:physical design, rectilinear Steiner minimal tree (RSMT), routing, ant colony optimization (ACO) |
|
