考虑长度限制的X结构Steiner最小树算法

郑瀚, 杨智宏, 刘耿耿

小型微型计算机系统 ›› 2025, Vol. 46 ›› Issue (10) : 2364 -2373.

PDF
小型微型计算机系统 ›› 2025, Vol. 46 ›› Issue (10) : 2364 -2373. DOI: 10.20009/j.cnki.21-1106/TP.2024-0374

考虑长度限制的X结构Steiner最小树算法

    郑瀚, 杨智宏, 刘耿耿
作者信息 +

Author information +
文章历史 +
PDF

摘要

长度限制Steiner最小树模型能够充分利用障碍内布线资源以进一步缩短总线长,进一步考虑X结构具有更好的线长优化效果,同时麻雀搜索算法具有良好的优化能力,本文基于动态种群麻雀搜索算法,提出了一种高质量的考虑长度限制的X结构Steiner最小树算法.首先,提出了一种基于动态种群机制改进麻雀搜索机制,通过动态调整种群结构以提高麻雀的多样性,避免算法过早陷入局部最优解.其次,提出了一种混合初始化策略以提高初始种群的多样性,有利于算法找到质量更佳的解.最后,提出了一种考虑角点复用的调整策略,通过在调整期间复用障碍物角点,有效缩短了绕行所需的线长.实验结果表明,相比于同类工作,本文所提出的算法能够取得良好的线长优化效果,证明了该算法的有效性,为电子设计自动化领域的布线优化提供了一种新的方法和思路.

关键词

Steiner最小树 / X结构 / 长度限制 / 超大规模集成电路 / 动态种群 / 麻雀搜索优化

Key words

引用本文

引用格式 ▾
考虑长度限制的X结构Steiner最小树算法[J]. 小型微型计算机系统, 2025, 46(10): 2364-2373 DOI:10.20009/j.cnki.21-1106/TP.2024-0374

登录浏览全文

4963

注册一个新账户 忘记密码

参考文献

AI Summary AI Mindmap
PDF

56

访问

0

被引

详细

导航
相关文章

AI思维导图

/