最短路径算法在电阻片落料系统中的应用

朱菊香

（常州铁道高等职业技术学校机电工程系，江苏 常州213011）

0 引言

落料是利用冲裁取得一定外形的制件或坯料的冲压方法，在电阻片生产中经常会用到这一制造工艺。以某公司PT06电阻片的生产为例，它需要经过两次落料，第一次落料一次剔除基板上的不合格品，第二次落料将基板上剩余的合格品一次性冲落。在第一次落料时，需要知道不合格电阻的位置，并以较短的时间或运动路径来冲除不合格品。

本文利用Prime最小生成树算法来解算冲压机构的最短运行路径，缩短了落料过程的时间，尤其在基板不良品较多时，效果明显。

1 落料系统的工作流程

整个落料系统是基于X—Y导轨结构的，包括机架、基板夹具、移动工作台、导轨、丝杠、气压冲头及步进电机等。PT06电阻片的基板为长方形的环氧树脂印制板，其上共印制了12行20列共240个碳膜电阻片。基板夹具用来放置待测的电阻片基板，在其下方按电阻片在基板上的位置排列了测试探针。

工作流程如下：（1）电阻片基板进入基板夹具定位；（2）测试探针升至测试高度；（3）系统扫描测试探针处的检测信号大小，获得每个电阻片的阻值及不合格品在基板上位置；（4）气压冲头到达基板上方，根据不合格品的位置信息冲落废品；（5）电阻片基板退出夹具，送至成品区批量落料。以上过程中耗时最多的便是冲落不合格品的过程。

2 不合格品的定位

基板上的电阻片是通过20路运算放大电路来采样的，每次采样采集某一行电阻片的阻值，这样共采样12次后便能获得所有240个电阻片的阻值。控制器通过控制20片多路模拟开关CD4067的通道地址，将12行的测试探针信号连接至运放电路。

通过两个参数便可判断不合格电阻片的位置信息。第一个参数为该电阻片所对应的CD4067的通道地址，第二个参数为该CD4067模拟输出端所对应的模数转换器的通道号。将这两个通道参数合并，便可得到不合格电阻片在基板上的位置，如图1所示。

图1 电阻片位置示意图

图中，左侧的0000～1100是CD4067的通道地址，0000代表选通第0个模拟通道，1100代表选通第11个模拟通道。CD4067的通道地址也代表了电阻片在基板上的行位置。上方AIN0～AIN19是20片CD4067模拟输出端对应的ADC通道号，代表了电阻片在基板上的列位置。若CD4067的第1个通道选通，则行码为0001，又发现PA7通道所对应的AD转换值超出了5%的范围，即模拟通道7的采样值超标，则转换成电阻片的位置为（1，7），即第1行、第7列。

3 最短路径解算

可通过行列码来储存不合格电阻片的位置信息。若CD4067的第1个通道选通，则行码为0001，又发现第7个通道的采样数据超出了合格范围，则第1行、第7列的电阻片为不合格品，记行列码为（1，7）。

为了缩短工作台移动的时间，节省电力和提高工作效率，需要对工作台的移动路径作出规划，即要找出一条最短路径，并将该路径存入不合格电阻片队列中供控制程序读取，使得按该队列顺序可在最短的时间内将不合格电阻片冲除。

图2为不合格电阻片组成的一个图数据结构示例。

图2 不合格电阻片组成的图结构

图中每个顶点代表一个不合格电阻片，顶点与顶点之间的权值为这两个电阻片之间的距离。如第1行第1列顶点与第3生成的。显然，遍历所有顶点的最短路径为（1，1）、（4，1）、（2，2）、（3，3）、（1，4）。

遍历所有顶点又使路径达到最短的算法在数据结构中被称为求解最小生成树。构造最小生成树有多种算法，这些算法往往都利用了最小生成树的 MST性质，即先假设N＝（V，｛E｝）为一个联通图，U是顶点集V的一个非空子集，若（u，v）是一条具有最小权值（最短路径）的边，则其中u∈U，v∈V－U，必存在一棵包含边（u，v）的最小生成树。

本设计采用的Prime算法即是利用MST性质求解最小生成树（最短路径）的算法。它假设N＝（V，｛E｝）是联通网，TE是N 上最小生成树中边的集合，Prime算法从U＝｛u0｝（u0∈V），TE＝｛空｝开始，重复执行下述操作：在所有u∈U，v∈V－U的边（u，v）∈E中找一条代价最小的边（u0，v0）并入TE，直至U＝V为止。

此时，TE中必有n－1条边，且T＝（V，｛TE｝）为N的最小生成树，也即本设计要求解的最短路径。

软件系统找出这一最短路径之后，将这些顶点（电阻片位置）的行列坐标按遍历次序存入一个队列当中，提供给步进电机控制模块读取。

为支持Prime算法，需要一个合适的数据结构来描述电阻片状态。一般情况下，图的数据结构可由邻接矩阵、邻接表或多重邻接表来表示。本设计中采用邻接表来存储图数据。若用邻接矩阵，因采用数组的方式来存储数据，所以需要占用240个存储单元，而不合格电阻片毕竟为数不多，因此会使邻接矩阵产生大量无用的“0”元素。而若采用链接存储结构的邻接表可避免这样的问题出现。邻接表的节点数可随不合格电阻片的数目动态调整。对于图2所示的情形，用邻接表来存储的形式如图3所示。图3表示的是一个无向重联通图，第一列框左边的序号代表节点编号，框内信息为不合格电阻片位置，右侧各框中的信息分别为节点编号、权值（节点间距离）、下一个节点的存储地址。

图3 不合格电阻片的邻接表结构

4 结语

大量试验表明，落料系统应用最短路径解算方法之后取得了较好的效果。最短路径求解的应用，有效缩短了气动冲压头在X—Y导轨上的移动行程，由此带来的好处不仅为缩短空程时间，电力消耗也得到降低，设备维护周期也变得更长。因电阻片产量巨大，即使在每个环节仅节省数十秒的空程时间，最后也能获得可观的经济效益。

［1］张晓敏．构建整体化的自动化测试平台［J］．中国高新技术企业，2010（22）：24－25．

［2］严蔚敏，吴伟民．数据结构（C语言版）［M］．北京：清华大学出版社，2011．

［3］王安敏，牛传猛，崔伟．基于X－Y工作平台的步进电机闭环控制系统［J］．微电机，2010，43（1）：103－105．

［4］殷人昆，陶永雷，谢若阳，等．数据结构（用面向对象方法与C＋＋语言描述）［M］．北京：清华大学出版社，1999．

［5］王昊，李昕．集成运放应用电路设计360例［M］．北京：电子工业出版社，2007．