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

doi:10.3778/j.issn.1002-8331.2008.20.007

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (20): 20-22.DOI: 10.3778/j.issn.1002-8331.2008.20.007

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

张瑾^1,2,马良¹

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

收稿日期:2008-03-06 修回日期:2008-04-18 出版日期:2008-07-11 发布日期:2008-07-11
通讯作者: 张瑾

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

摘要/Abstract

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

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

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

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

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]	李伟，张鑫龙. 考虑个体行为的改进CA模型人员疏散研究[J]. 计算机工程与应用, 2021, 57(17): 275-282.
[2]	滕婕，夏志杰，占欣. 基于改进CA模型的群体辟谣信息扩散效果预测[J]. 计算机工程与应用, 2020, 56(6): 51-57.
[3]	齐姗姗，彭其渊. 改进的元胞自动机列车交通流仿真模型研究[J]. 计算机工程与应用, 2019, 55(24): 254-258.
[4]	张生，李玉清，李源庆臻. 结合用户感知模型的多值CA仿真及应用[J]. 计算机工程与应用, 2019, 55(20): 250-256.
[5]	贺红，陈永. 考虑前车动态效应的高速跟驰交通流研究[J]. 计算机工程与应用, 2019, 55(14): 209-214.
[6]	李立，邢婷婷，王佳. 基于改进蚁群算法的CA的应用——以土地利用模拟为例[J]. 计算机工程与应用, 2018, 54(20): 253-258.
[7]	袁野1，田中旭2. 隧道火灾疏散模型实时仿真算法的实现[J]. 计算机工程与应用, 2017, 53(23): 208-211.
[8]	张小炳，祝俪菱，杨达. 基于CA模型的上坡道小汽车-卡车交通拥堵特性[J]. 计算机工程与应用, 2017, 53(19): 216-223.
[9]	吴丽鑫，郑智捷. 变值编码下元胞自动机分类模式可视化分析[J]. 计算机工程与应用, 2017, 53(10): 160-164.
[10]	杨福龙1，曹佳1，白夜2. 基于元胞自动机的林火蔓延三维模拟仿真研究[J]. 计算机工程与应用, 2016, 52(19): 37-41.
[11]	王朝斌1，毛乾任2，向婷3，邓超2. 移动元胞自动机的个体化网络舆情聚类模型与仿真[J]. 计算机工程与应用, 2016, 52(19): 122-127.
[12]	胡志飞，段中兴，陈胜，刘阳. 地铁车站疏散照明指示系统的引导作用研究[J]. 计算机工程与应用, 2016, 52(15): 237-242.
[13]	刘晓斌，杨贯中，欧阳柳波，李勇军. 软件体系结构动态演化的元胞自动机模型研究[J]. 计算机工程与应用, 2015, 51(9): 87-92.
[14]	文杏梓1，刘友金1，欧阳军林2. 软件可信性演化的移动元胞自动机模拟[J]. 计算机工程与应用, 2015, 51(7): 12-17.
[15]	刘应东，牛惠民，王建强，李世威. 无信号人行横道交通流特性的研究[J]. 计算机工程与应用, 2015, 51(6): 16-21.

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

Solving rectilinear Steiner minimum tree problem by improved cellular ant algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics