| 结合改进A*算法与拆线重布的有序逃逸布线 |
| |
| 引用本文： | 邓新国,叶似锦,陈家瑞,陈传东.结合改进A*算法与拆线重布的有序逃逸布线[J].电子与信息学报,2022,43(6):1609-1616. |
| |
| 作者姓名： | 邓新国 叶似锦 陈家瑞 陈传东 |
| |
| 作者单位： | 福州大学数学与计算机科学学院 福州 350108;福州大学物理与信息工程学院 福州 350108 |
| |
| 摘 要： | 逃逸布线是印刷电路板设计的一个重要组成部分.针对并行逃逸布线的方法用于较大规模电路板布线时速度慢且结果不够好的问题,该文提出一种结合改进A*算法与拆线重布的有序逃逸布线方法.首先,通过代价预估函数确定引脚的布线顺序,使用改进A*算法初始化有序逃逸布线.接着,优化同长度布线路径,调整拥挤区域布线路径.最后,使用A*算法和广度优先搜索进行拆线重布.实验结果表明,该方法对给出的所有测试用例都实现了100％的逃逸,得到有序逃逸路径的可行解非常接近最优解,CPU时间比布尔可满足性问题(SAT)算法与最小费用多商品流(MMCF)算法平均减少分别约为95.6％,?97.8％,总体线长也接近最优.提出的方法能够明显减少寻找可行解的时间,提高布线质量.
|
| 关 键 词： | A*算法 拆线重布 有序逃逸布线 最短路径 |
Ordered Escape Routing Combining Improved A*Algorithm with Rip-up and Reroute |
| |
| DENG Xinguo,YE Sijin,CHEN Jiarui,CHEN Chuandong.Ordered Escape Routing Combining Improved A*Algorithm with Rip-up and Reroute[J].Journal of Electronics & Information Technology,2022,43(6):1609-1616. |
| |
| Authors: | DENG Xinguo YE Sijin CHEN Jiarui CHEN Chuandong |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
