考虑布线资源松弛的X结构Steiner最小树算法

作     者：汤浩 刘耿耿 郭文忠 陈国龙 TANG Hao;LIU Genggeng;GUO Wenzhong;CHEN Guolong

作者机构：福州大学数学与计算机科学学院福州350116 福州大学福建省网络计算与智能信息处理重点实验室福州350116 福州大学空间数据挖掘与信息共享教育部重点实验室福州350108 

出 版 物：《模式识别与人工智能》 (Pattern Recognition and Artificial Intelligence)

年 卷 期：2020年第33卷第5期

页      面：401-412页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金项目(No.61877010,11501114) 福建省自然科学基金项目(No.2019J01243)资助 

主　　题：Steiner最小树 X结构布线 粒子群优化 角点选取 精炼策略 

摘      要：为了进一步考虑X结构,并充分利用障碍内可用布线资源,文中提出考虑布线资源松弛的X结构Steiner最小树算法.为了能够求解离散问题,在粒子的更新操作中引入交叉算子和变异算子.通过构建查找表,为整个算法流程提供快速的信息查询.提出角点选取策略,通过引入一些障碍角点,使粒子满足约束.最后构建精炼策略,进一步提高最终布线树的质量.实验表明,文中算法充分利用障碍内可用布线资源,有效缩短总布线长度,取得较佳的总布线长度.