Solving rectilinear Steiner minimum tree problem by improved cellular ant algorithm

doi:10.3778/j.issn.1002-8331.2008.20.007

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (20): 20-22.DOI: 10.3778/j.issn.1002-8331.2008.20.007

• 博士论坛 • Previous Articles Next Articles

Solving rectilinear Steiner minimum tree problem by improved cellular ant algorithm

ZHANG Jin^1,2,MA Liang¹

1.School of Management，University of Shanghai for Science and Technology，Shanghai 200093，China
2.Computer and Information Engineering College，Henan University，Kaifeng，Henan 475001，China

Received:2008-03-06 Revised:2008-04-18 Online:2008-07-11 Published:2008-07-11
Contact: ZHANG Jin

求解绝对值距离Steiner最小树的改进元胞蚂蚁算法

张瑾^1,2,马良¹

1.上海理工大学管理学院，上海 200093
2.河南大学计算机与信息工程学院，河南开封 475001

通讯作者: 张瑾

Abstract

Abstract: The rectilinear Steiner minimum tree problem is a classical NP-complete problem of combinatorial optimization which has been widely used in the layout of integrated circuit etc.This paper designed an improved cellular automata ant algorithm based on the discovery of the similar structure between the cellular automata and the search area of the rectilinear Steiner minimum tree.The computational results showed that this algorithm can improve the total length about 15% than that of the minimum spanning tree，so the effectiveness of the algorithm has been validated.

Key words: Rectilinear Steiner Minimum Tree（RSMT）, cellular automata, ant algorithm

摘要： 绝对值距离Steiner最小树问题是在集成电路布线等领域应用广泛的属于NP难的经典组合优化问题，由于该问题的搜索空间与元胞自动机的结构相似，设计了求解绝对值距离Steiner最小树问题的改进的元胞蚂蚁算法。经大量数据实验表明，该算法要比最小生成树平均改进15%，优于多数已有的基于最小生成树的近似算法，验证了算法的实用性。

关键词: 绝对值距离Steiner最小树, 元胞自动机, 蚂蚁算法

ZHANG Jin^1,2,MA Liang¹. Solving rectilinear Steiner minimum tree problem by improved cellular ant algorithm[J]. Computer Engineering and Applications, 2008, 44(20): 20-22.

张瑾^1,2,马良¹. 求解绝对值距离Steiner最小树的改进元胞蚂蚁算法[J]. 计算机工程与应用, 2008, 44(20): 20-22.

[1]	ZHANG Sheng, LI Yuqing, LI Yuanqingzhen. Multi-Value Cellular Automata Simulation and Application Combined with User Perception Model [J]. Computer Engineering and Applications, 2019, 55(20): 250-256.
[2]	HE Hong, CHEN Yong. HE Hong, CHEN Yong [J]. Computer Engineering and Applications, 2019, 55(14): 209-214.
[3]	ZHANG Xiaobing, ZHU Liling, YANG Da. Characteristics of car-truck traffic flow on up-slope based on CA model [J]. Computer Engineering and Applications, 2017, 53(19): 216-223.
[4]	WU Lixin, ZHENG Jeffrey. Visual analysis of classification of cellular automata based on variant coding scheme [J]. Computer Engineering and Applications, 2017, 53(10): 160-164.
[5]	WANG Chaobin1, MAO Qianren2, XIANG Ting3, DENG Chao2. Mobile cellular automata of individualized network public opinion clustering model and simulation [J]. Computer Engineering and Applications, 2016, 52(19): 122-127.
[6]	HU Zhifei, DUAN Zhongxing, CHEN Sheng, LIU Yang. Study on guiding role of evacuation lighting and directing system of subway station [J]. Computer Engineering and Applications, 2016, 52(15): 237-242.
[7]	LIU Xiaobin, YANG Guanzhong, OUYANG Liubo, LI Yongjun. Research in dynamic evolution of software architectures based on cellular automata model [J]. Computer Engineering and Applications, 2015, 51(9): 87-92.
[8]	WEN Xingzi1, LIU Youjin1, OUYANG Junlin2. Simulating software trustworthiness evolution based on moving cellular automata [J]. Computer Engineering and Applications, 2015, 51(7): 12-17.
[9]	ZHAO　Yanxin, WANG Xiaoming, LI Li. Virus spreading model on complex networks based on cellular automata [J]. Computer Engineering and Applications, 2015, 51(10): 117-122.
[10]	FU Xiuwen, LI Wenfeng, SONG Wei, YANG Lin. Analysis of invulnerability of wireless sensor networks based on cellular automata [J]. Computer Engineering and Applications, 2014, 50(8): 1-5.
[11]	HU Xiaohui1, TIAN Qiyuan1, CHEN Yong1, LI Xin2. Simulation of urgent evacuation in high-speed trains interior [J]. Computer Engineering and Applications, 2014, 50(4): 250-253.
[12]	KUANG Lidan, DENG Qingyong, LI Zhetao. New method for estimating SOC of lithium battery [J]. Computer Engineering and Applications, 2013, 49(6): 249-252.
[13]	ZHANG Jianming, LIU Haiyan, SUN Shumin. Key frame extraction based on improved ant algorithm and agglomerative [J]. Computer Engineering and Applications, 2013, 49(3): 222-225.
[14]	CAO Aichun1, YANG Xiaoting2, HOU Xudong3. Crowd evacuation model for large sports venues based on multi-Agent and Cellular Automata technology [J]. Computer Engineering and Applications, 2013, 49(24): 229-232.
[15]	LU Kuan, LI Dongmei, YU Jing, WANG Jianxin. Intelligent test paper construction method based on cellular genetic algorithm [J]. Computer Engineering and Applications, 2013, 49(16): 57-60.

Solving rectilinear Steiner minimum tree problem by improved cellular ant algorithm

求解绝对值距离Steiner最小树的改进元胞蚂蚁算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics