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 Jin1,2,MA Liang1   

  1. 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   

  1. 1.上海理工大学 管理学院,上海 200093
    2.河南大学 计算机与信息工程学院,河南 开封 475001
  • 通讯作者: 张 瑾

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最小树, 元胞自动机, 蚂蚁算法