多级规约算法在PCB钻孔路径优化中的应用
程森林;曾伟
【期刊名称】《计算机工程与应用》 【年(卷),期】2012(048)016
【摘要】The PCB(Printed Circuit Board) path optimization is a large-scale TSP(Traveling Salesman Problem) problem. An Enhanced Multilevel Reduction algorithm (EMR) is proposed to solve this problem. The proposed algorithm redesigns the reduction operator and brings a control parameter to improve its flexibility. Meanwhile, in view of the difficulties of saving the results produced by reduction operator, a new data structure like human family tree is presented. Experimental results, compared with the other method, demonstrate that EMR outperforms in practicability and generality with higher quality and efficiency of optimization.%以求解PCB(Printed Circuit Board)钻孔路径优化这一大规模复杂的TSP(Traveling Salesman Problem)问题为背景,研究了一种改进的多级规约算法(EMR).该算法依据工程应用中实用性、通用性的特点重新设计了多级规约算法(MR)的规约和细化算子并增加了控制参数以提高算法的灵活性;针对算法中会产生大量部分解集且难以储存这一问题,设计了一种类似人类族谱的数据结构.实验结果以及与循环LK算法和蚁群算法的对比分析表明,EMR算法兼顾了实用性和通用性,且有较高的优化质量和优化效率. 【总页数】4页(212-215)
【关键词】旅行商问题TSP;印制线路板PCB;多级归约算法;路径优化
多级规约算法在PCB钻孔路径优化中的应用
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)