飞针测试机开路测试路径优化方法

摘要

本发明提供一种飞针测试机开路测试路径优化方法，其特征在于：所述方法包括如下步骤：A、读取并整理路径优化所需要的信息；B、循环对每个网络的点进行配对，然后再将配对合并；B1、建立第一至第十三容器；B2、分别从正面可测试点容器、反面可测试点容器中读取同一个网络的正面点及反面点，分别保存到第一容器、第二容器中；B3、对第一、二容器中的点重新排序；B4、进行开路配对；B7、配对合并，合并后放入第十三容器中；C、开路优化；D、生成测试文件：开路优化完成后，生成新的CONTI.LST文件；本发明比现有的软件在测试时间上可优化30％，测试时间可缩短50％；可广泛应用于印制电路板制造行业及测试行业。

权利要求

1.一种飞针测试机开路测试路径优化方法，其特征在于：所述方法包括如下步骤：A、读取并整理路径优化所需要的信息；

B、循环对每个网络的点进行配对，然后再将配对合并：

B1、建立第一至第十三容器，其中，第七、第八、第九、第十、第十一和第十二容器用于保存配对结果，第十三容器用于保存配对合并后的结果；

B2、分别从正面可测试点容器、反面可测试点容器中读取同一个网络的正面点及反面点，分别保存到第一容器、第二容器中；

B3、对第一、二容器中的点重新排序：

B31、分别将第一容器、第二容器中的点按x坐标从小到大排列，再将容器中的点分成左面点和右面点两部分；将第一容器中的左面点和右面点分别放入第三容器和第四容器中；

将第二容器中的左面点和右面点分别放入第五容器和第六容器中；再分别对第三容器、第四容器、第五容器、第六容器的点按最近邻法则进行排序；然后将第一容器、第二容器清空；

再将第三容器与第四容器中的点放入第一容器中，第五容器与第六容器的点放入第二容器中；

B4、进行开路配对：

B41、当前网络只有正面点或只有反面点时进行单面配对；当前网络既有正面点也有反面点时，进行双面点配对；

当网络只有正面点时，按以下方法进行单面点配对：

B411、定义变量i为第一容器的索引，初始值为0即指向第一容器的第一个点，从第一容器的第一个点开始依次向后，当i为0或者i为偶数的时候，配对情况为第一容器中第i结点和第一容器中第i+1结点，当i>0并且i为奇数的时候，配对情况为第一容器中第i+1结点和第一容器中第i结点；将配对放入第九容器；当索引指向第一容器中倒数第二个点时结束配对，配对完成；

B42、当配对的结果为有正、反面各两个点时，保存在第七容器中；当配对的结果为有正、反面各一个点时，保存在第八容器中；当配对的结果为只有正面点时，保存在第九容器中；当配对的结果为只有反面点时，保存在第十容器中；当配对的结果为有两个正面点和一个反面点时，保存在第十一容器中；当配对的结果为有一个正面点和两个反面点时，保存在第十二容器中；

当前网络既有正面点也有反面点时，按以下方法进行双面点配对：

B412、当正面点数大于1，反面点数为1时,配对方法为：将反面点作为“公共点”，分别从第三容器、第四容器中取出第一个点，与反面点进行配对，结果放入第十一容器中；重复以上步骤直到第三容器，第四容器中的最后一个点；若其中一个容器比另一个容器多一个点，则将多一个点的那个容器的最后一个点与反面点进行配对，配对结果放入第八容器中；

B413、当反面点数大于1，正面点数为1时,配对方法为：将正面点作为“公共点”，分别从第五、第六容器中取出第一个点，与正面点配对，结果放入第十二容器中；重复以上步骤直到第五容器，第六容器中的最后一个点；若其中一个容器比另一个容器多一个点，则将多一个点的那个容器的最后一个点与正面点进行配对，配对结果放入第八容器中；

B414、当正、反面的点数都大于1，并且 时，配对方法为：

①、定义变量j为第二、三、四容器的索引，初始值为0即指向第二、三、四容器的第一个点；

②、当j≤反面点数-2并且j为偶数的时候，按照第三容器第j点、第四容器第j点、第二容器第j点、第二容器第j+1点的顺序进行配对，配对为两个正面点和两个反面点，放入第七容器中；

当j≤反面点数-2并且j为奇数的时候，按照第三容器第j点、第四容器第j点、第二容器第j+1点、第二容器第j点的顺序进行配对，配对为两个正面点和两个反面点，放入第七容器中；

当j＞反面点数-2时，按照第三容器第j点、第四容器第j点、第二容器最后一个点的顺序进行配对，配对结果为两个正面点和一个反面点，放入第十一容器中；

重复上述步骤，直到

③、当 也就是最后一次配对时，如果正面点数为奇数，配对结果为第四容器的最后一个点、第二容器的最后一个点，即一个正面点和一个反面点，保存到第八容器中；如果正面点数为偶数，配对结果为第三容器的最后一个点、第四容器的最后一个点、第二容器的最后一个点，即两个正面点和一个反面点，放入第十一容器中；

B415、当正、反面点数都大于1，并且当 时，配对方法如下：①定义变量k为第一、五、六容器的索引，初始值为0即指向第一、五、六容器的第一个点；

②、当k≤正面点数-2，并且k为偶数的时候，按照第一容器第k点、第一容器第k+1、第五容器第k点、第六容器第k点的顺序进行配对，配对为配对为两个正面点和两个反面点，放入第七容器中；

当k≤正面点数-2并且k为奇数的时候，按照第一容器第k+1点、第一容器第k点、第五容器第k点、第六容器第k点的顺序进行配对，配对为配对为两个正面点和两个反面点，放入第七容器中；

当k＞正面点数-2时，按照第一容器最后一个点、第五容器第k点、第六容器第k点的顺序进行配对，配对为两个正面点和一个反面点，放入第十一容器中；

重复上述步骤直到

③、当 也就是最后一次配对时，如果反面点数为奇数，将第一容器最后一个点、第六容器最后一个点，配对为一个正面点和一个反面点，反应保存到第八容器中；

如果反面点数为偶数，将第一容器最后一个点、第五容器最后一个点、第六容器最后一个点，配对为两个正面点和一个反面点，放入第十一容器中；

B416、当网络只有一个正面点和一个反面点时，则将这两个点配对放入第八容器中；

B5、当前网络处理完成后清空第一、第二、第三、第四、第五、第六容器，并将反面可测试点容器中的所有第二容器中的点删除,正面可测试点容器中的所有第一容器中的点删除；

B6、判断正、反面可测试点容器是否都为空，若不为空，重复B2、B3、B4、B5步骤；若为空，执行B7；

B7、配对合并：

B71、取出第八容器中的两个配对合并成行，保存至第十三容器中；

B72、取出第七容器中的一个配对成行，保存至第十三容器中；

B73、判断第九容器是否为空，当第九容器不为空时判断第十容器是否为空，若第十容器也不为空，则分别从第九容器、第十容器中取出一配对合并成行后放入第十三容器中；

B74、若第九容器不为空，第十容器为空，则将第九容器中配对取出，合成一行后放入第十三容器中；

B75、若第九容器为空，第十容器不为空，则将第十容器中的配对取出，合成一行后放入第十三容器中；

B76、取出第十一容器中的配对成行后保存至第十三容器中；

B77、取出第十二容器中的配对成行后保存至第十三容器中；

B78、重复B71、B72、B73、B74、B75、B76、B77直到合并完成；

C、开路优化：

C1、初始化链表，读取第十三容器中的第一行的信息，并对链表第一个结点进行初始化，初始化完成后在第十三容器中删除该行；

C2、定义一个整数型变量min用于保存第十三容器中的行到当前链表最后行的距离最小值，并定义初始值为零；再定义一个整数型变量index，用于保存距离等于min的行在第十三容器中所对应的位置；

C3将min赋值为0，index赋值为1；

C4、继续读取第十三容器中的下一行信息，计算它与链表中当前行的距离，若当前距离小于min则将当前距离赋值给min，并将当前位置索引号赋值给index；若当前距离大于min则计算下一个节点；

C5、判断是否遍历完第十三容器，若遍历完，则将index所指的第十三容器中的行链接到链表的末尾，并删除index所指的第十三容器中的行，然后执行C6；若没遍历完，则继续执行步骤C4；

C6、判断第十三容器是否为空，若为空，执行步骤D；若不为空，返回执行步骤C3；

D、生成测试文件：开路优化完成后，生成新的CONTI.LST文件。

说明书

飞针测试机开路测试路径优化方法

技术领域

[0001] 本发明涉及印制板测试技术领域，尤其涉及一种飞针测试机开路测试路径优化方法。

背景技术

[0002] 印刷电路板(PCB)是集成各种电子元器件的信息载体，在各个领域得到了广泛的应用。随着技术的不断发展和工业的持续进步，电子产品趋于更轻、更薄、更短、更小，也使得PCB制造技术朝更高密度发展。在高度自动化的生产现场如何高效得检测高密度PCB以及降低检测成本，一直是研究人员的难题。目前，我国在生产PCB过程中的测试手段比较单一，其中飞针测试是一种主要的测试手段，但现有的飞针测试机运行效率低下、操作流程复杂、错检率也高。为了改善这种情况，发明一种能够生成高效、稳定、精确的PCB检测路径算法就成为一项具有现实意义的紧迫任务。

[0003] 飞针测试机是一个在制造环境测试PCB(印刷电路板)的系统。它用探针代替车床，在X-Y机构上装有4-8个由电机驱动的可分别快速移动的探针，利用探针在Z方向的移动同PCB的焊点进行接触并进行电气测量。测试人员把设计工程师的CAD数据转换成可使用的文件，这些文件包含了需要测试的焊点的坐标(X，Y)及焊点在PCB中的网络值，由此决定驱动各个探针的X、Y、Z电机的移动.通常，一块PCB上可能有上千个焊点，如果探针不按一种最优或较优的路径移动进行测试，可能会耗费数倍的测试时间，延误生产。把旅行商问题即TSP问题应用到该系统上，很好的解决了探针移动轨迹优化的问题。TSP属于组合数学中一个古老而又困难的问题。有效的解决它，在可计算理论上具有重要的理论意义，同时也具有重要的实际应用价值。目前解决此类问题常用的算法有遗传算法、模拟退火算法等。但是他们并没有很好的根据飞针测试仪的特点来建立模型，因为时间复杂的太高而未达到很好的效率。

发明内容

[0004] 本发明所要解决的技术问题是提供一种飞针测试机开路测试路径优化方法。

[0005] 根据本发明的一种技术方案，一种飞针测试机开路测试路径优化方法，其特征在于：所述方法包括如下步骤：

[0006] A、读取并整理路径优化所需要的信息：

[0007] B、循环对每个网络的点进行配对，然后再将配对合并：

[0008] B1、B1、建立第一至第十三容器，其中第七、第八、第九、第十、第十一和第十二容器保存配对结果，第十三容器用于保存配对合并后的结果；

[0009] B2、分别从正面可测试点容器、反面可测试点容器中读取同一个网络的正面点及反面点，分别保存到第一容器、第二容器中；

[0010] B3、对第一、二容器中的点重新排序：

[0011] B31、B31、分别将第一容器、第二容器中的点按x坐标从小到大排列，再将容器中的点分成左面点和右面点两部分；将第一容器中的左面点和右面点分别放入第三容器和第四容器中；将第二容器中的左面点和右面点分别放入第五容器和第六容器中；再分别对第三容器、第四容器、第五容器、第六容器的点按最近邻法则进行排序；然后将第一容器、第二容器清空；再将第三容器与第四容器中的点放入第一容器中，第五容器与第六容器的点放入第二容器中；

[0012] B4、进行开路配对：

[0013] B41、当前网络只有正面点或只有反面点时进行单面配对；当前网络既有正面点也有反面点时，进行双面点配对；

[0014] B42、当配对的结果为有正、反面各两个点时，保存在第七容器中；当配对的结果为有正、反面各一个点时，保存在第八容器中；当配对的结果为只有正面点时，保存在第九容器中；当配对的结果为只有反面点时，保存在第十容器中；当配对的结果为有两个正面点和一个反面点时，保存在第十一容器中；当配对的结果为有一个正面点和两个反面点时，保存在第十二容器中；

[0015] B5、当前网络处理完成后清空第一、第二、第三、第四、第五、第六容器，并将反面可测试点容器中的所有第二容器中的点删除,正面可测试点容器中的所有第一容器中的点删除；

[0016] B6、判断正、反面可测试点容器是否都为空，若不为空，重复B2、B3、B4、B5步骤；若为空执行B7；

[0017] B7、配对合并，合并后放入第十三容器中；

[0018] C、开路优化：

[0019] D、生成测试文件：开路优化完成后，生成新的CONTI.LST文件。

[0020] 根据本发明所述的飞针测试机开路测试路径优化方法的一个优选方案，开路优化按以下步骤进行：

[0021] C1、初始化链表，读取第十三容器中的第一行的信息，并对链表第一个结点进行初始化，初始化完成后在第十三容器中删除该行；

[0022] C2、定义一个int型变量(整数型变量)min用于保存第十三容器中的行到当前链表最后行的距离最小值，并定义初始值为零；再定义一个int型变量index，用于保存距离等于min的行在第十三容器中所对应的位置；

[0023] C3将min赋值为0，index赋值为1；

[0024] C4、继续读取第十三容器中的下一行信息，计算它与链表中当前行的距离，若当前距离小于min则将当前距离赋值给min，并将当前位置索引号赋值给index；若当前距离大于min则计算下一个节点；

[0025] C5、判断是否遍历完第十三容器，若遍历完，则将index所指的第十三容器中的行链接到链表的末尾，并删除index所指的第十三容器中的行，然后执行C6；若没遍历完则继续执行C4；

[0026] C6、判断第十三容器是否为空，若为空,表示链表已排好序，最终路径已生成，执行D；若不为空表示路径还没完全生成，重复执行C2、C3、C4；

[0027] 根据本发明的所述的飞针测试机开路测试路径优化方法的一个优选方案，步骤B41中，当网络只有正面点时，按以下方法进行单面点配对：

[0028] B411、定义变量i为第一容器的索引，初始值为0即指向第一容器的第一个点，从第一容器的第一个点开始依次向后，当i为0或者i为偶数的时候，配对情况为第一容器中第i结点和第第一容器中第i+1结点，当i>0并且i为奇数的时候，配对情况为第一容器中第i+1结点和第一容器中第i结点；将配对放入第九容器；当索引指向第一容器中倒数第二个点时结束配对，配对完成。

[0029] 同理，当网络只有反面点时反面测试点配对方法同正面测试点配对方法，不同之处在于定义变量i为第二容器的索引，初始值为0即指向第二容器的第一个点，配对结果放入第十容器中。

[0030] 根据本发明的所述的飞针测试机开路测试路径优化方法的一个优选方案，步骤B41中，当前网络既有正面点也有反面点时，进行双面点配对；方法如下：

[0031] B412、当正面点数大于1，反面点数为1时,配对方法为：将反面点作为“公共点”，分别从第三容器、第四容器中取出第一个点，与反面点进行配对，结果放入第十一容器中；重复以上步骤直到第三容器，第四容器中的最后一个点；若其中一个容器比另一个容器多一个点，则将多一个点的那个容器的最后一个点与反面点进行配对，配对结果放入第八容器中；

[0032] B413、当反面点数大于1，正面点数为1时,配对方法为：将正面点作为“公共点”，分别从第五、第六容器中取出第一个点，与正面点配对，结果放入第十二容器中；重复以上步骤直到第五容器，第六容器中的最后一个点；若其中一个容器比另一个容器多一个点，则将多一个点的那个容器的最后一个点与正面点进行配对，配对结果放入第八容器中；

[0033] B414、当正、反面的点数都大于1，并且 时，配对方法为：

[0034] ①、定义变量j为第二、三、四容器的索引，初始值为0即指向第二、三、四容器的第一个点；

[0035] ②、当j≤反面点数-2并且j为偶数的时候，按照第三容器第j点、第四容器第j点、第二容器第j点、第二容器第j+1点的顺序进行配对，配对为两个正面点和两个反面点，放入第七容器中；

[0036] 当j≤反面点数-2并且j为奇数的时候，按照第三容器第j点、第四容器第j点、第二容器第j+1点、第二容器第j点的顺序进行配对，配对为两个正面点和两个反面点，放入第七容器中；

[0037] 当j＞反面点数-2时，按照第三容器第j点、第四容器第j点、第二容器最后一个点的顺序进行配对，配对结果为两个正面点和一个反面点，放入第十一容器中。

[0038] 重复上述步骤直到

[0039] ③、当 也就是最后一次配对时，如果正面点数为奇数，配对结果为第四容器的最后一个点、第二容器的最后一个点，即一个正面点和一个反面点，保存到第八容器中；如果正面点数为偶数，配对结果为第三容器的最后一个点、第四容器的最后一个点、第二容器的最后一个点，即两个正面点和一个反面点，放入第十一容器中。

[0040] B415、进行双面点配对时，当正反面点数都大于1，并且当时，配对方法如下：

[0041] ①定义变量k为第一、五、六容器的索引，初始值为0即指向第一、五、六容器的第一个点；

[0042] ②、当k≤正面点数-2，并且k为偶数的时候，按照第一容器第k点、第一容器第k+1、第五容器第k点、第六容器第k点的顺序进行配对，配对为配对为两个正面点和两个反面点，放入第七容器中；

[0043] 当k≤正面点数-2并且k为奇数的时候，按照第一容器第k+1点、第一容器第k点、第五容器第k点、第六容器第k点的顺序进行配对，配对为配对为两个正面点和两个反面点，放入第七容器中；

[0044] 当k＞正面点数-2时，按照第一容器最后一个点、第五容器第k点、第六容器第k点的顺序进行配对，配对为两个正面点和一个反面点，放入第十一容器中；

[0045] 重复上述步骤直到

[0046] ③、当 也就是最后一次配对时，如果反面点数为奇数，将第一容器最后一个点、第六容器最后一个点，配对为一个正面点和一个反面点，反应保存到第八容器中；如果反面点数为偶数，将第一容器最后一个点、第五容器最后一个点、第六容器最后一个点，配对为两个正面点和一个反面点，放入第十一容器中；

[0047] B416、当网络只有一个正面点和一个反面点时，则将这两个点配对放入第八容器中。

[0048] 根据本发明的所述的飞针测试机开路测试路径优化方法的一个优选方案，步骤B7按方法如下进行配对合并：

[0049] B71、取出第八容器中的两个配对合并成行保存至第十三容器中；

[0050] B72、取出第七容器中的一个配对成行保存至第十三容器中；

[0051] B73、判断第九容器是否为空，当第九容器不为空时判断第十容器是否为空，若第十容器也不为空，则分别从第九容器、第十容器中取出一配对合并成行后放入第十三容器中；

[0052] B74、若第九容器不为空，第十容器为空，则将第九容器中配对取出，合成一行后放入第十三容器中；

[0053] B75、若第九容器为空，第十容器不为空，则将第十容器中的配对取出，合成一行后放入第十三容器中；

[0054] B76、取出第十一容器中的配对成行后保存至第十三容器中；

[0055] B77、取出第十二容器中的配对成行后保存至第十三容器中；

[0056] B78、重复B71、B72、B73、B74、B75、B76、B77,直到合并完成。

[0057] 本发明所述的印制电路板测试路径优化方法的有益效果是：本发明先从待优化conti.lst文件中提取所有有效点，并按照“网络号正反面标志x坐标y坐标”的格式定义点信息，在满足飞针测试机运行规则的前提下，对所有点进行配对，然后重新生成路径；经过实际大量的测试，结果表明比现有的软件在测试时间上可优化30％，测试时间可缩短50％；优化的conti.lst文件行数越多，其优化结果越明显。本发明可广泛应用于印制电路板制造行业及测试行业。

附图说明

[0058] 以下将结合附图对本发明的实施例作进一步的说明。

[0059] 图1是飞针测试机开路测试路径优化方法流程图。

[0060] 图2是conti.lst文件格式示意图。

[0061] 图3是本发明的读取conti.lst文件并整理路径优化所需信息流程图。

[0062] 图4是本发明循环对每个网络进行配对，并合并配对流程图。

[0063] 图5是本发明开路配对流程图。

[0064] 图6是本发明中步骤B414的配对函数流程图。

[0065] 图7是本发明当中配对合并流程图。

[0066] 图8是本发明中开路优化流程图。

[0067] 图9是具体实施例中双面点配对的conti.lst文件格式示意图。

[0068] 图10是具体实施例中合并配对点的conti.lst文件格式示意图。

具体实施方式

[0069] 参见图1，一种飞针测试机开路测试路径优化方法，所述方法包括如下步骤：

[0070] A、读取并整理路径优化所需要的信息，具体操作流程可参见图3所示，在具体实施例中可按步骤A1～A6进行：

[0071] A1、逐行读取需要进行优化的conti.lst文件，提取每行中的正、反面有效点，并将其放入正面可测试点容器以及反面可测试点容器中；

[0072] 飞针测试机通过读取conti.lst文件作为输入，我们对原有的文件进行优化，生成新的conti.lst文件，conti为文件名中的关键字，文件名可命名为continew等，.lst为文件的格式名。可以通过对比原有conti.lst文件和新的conti.lst文件的总移动距离来对比优化效果。

[0073] conti.lst文件的文件每一行都不会超过68个字符，对于每个字符位都有严格的定义，其中包含大量信息，包括文件行数、网络号，点的类型信息，点的坐标等conti.lst文件格式参见图2。

[0074] 文件的第一行为注释，第二行开始为数据行，每行总字符数为68，从第二行开始到最后一行格式如下。

[0075] Columns 1-5、18-22、35-39、52-56为网络号；

[0076] Columns 6、23、40、57为点的类型，c代表正面点，s代表反面点，h代表孔；

[0077] Columns 7-11、24-28、41-45、58-62为点的x轴坐标；

[0078] Columns 13-17、29-33、47-51、64-68为点的y轴坐标；

[0079] 由于PCB板大多为多层板，所以孔是必不可少的。我们这里对孔的处理方法为，若孔在Columns 6、23的位置上，则将其放在正面可测试点容器中，若孔在Columns 40、57的位置上，则将其放在反面可测试点容器中。

[0080] A2、去除正面可测试点容器以及反面可测试点容器中的重复点；

[0081] 因为在读原conti.lst文件时，原文件中包含配对关系，所以会出现重复的点，所以要在读取conti.lst文件后去除重复点。

[0082] B、循环对每个网络的点进行配对，然后再将配对合并；具体操作流程参见图4所示。

[0083] PCB板的表面上分布了N个点，根据导通关系，我们可以将这些点分为多个网络，每个网络内部的任意两点之间都应该导通；任意两个不同网络之间都应该绝缘。一个网络中的点可以只出现在正面或者反面，也可以同时出现在正、反面上。

[0084] B1、建立第一至第十三容器；第七、第八、第九、第十、第十一和第十二容器用于保存配对结果，第十三容器用于保存配对合并后的结果；

[0085] 即建立第七容器保存两正两反的配对结果，建立第八容器保存一正一反的配对结果，建立第九容器保存两正零反的配对结果，建立第十容器保存零正两反的配对结果，建立第十一容器保存两正一反的配对结果，建立第十二容器保存一正两反的配对结果。建立第十三容器用于保存配对合并后结果即conti.lst文件的行。

[0086] B2、分别从正面可测试点容器、反面可测试点容器中读取同一个网络的正面点及反面点，分别保存到第一容器、第二容器中；

[0087] 所有正面点保存在正面可测试点容器中，同理所有反面点保存在反面可测试点容器中，若被测试的PCB板为单面板，则正面可测试点容器或者反面可测试点容器为空。第一容器保存当前所处理的网络的正面点，第二容器保存当前所处理网络的反面点。若当前网络为单面网络则第一容器或第二容器为空。

[0088] B3、对于第一、二容器中的点重新排序：

[0089] B31、分别将第一容器、第二容器中的点按x坐标从小到大排列，然后以x坐标居中的点为界，再将容器中的点分成左面点和右面点两部分，左面点的x坐标小于中点的x坐标，右面点的x坐标大于中点的x坐标；将第一容器中的左面点和右面点分别放入第三容器、第四容器中；将第二容器中的左面点和右面点分别放入第五容器、第六容器中；再分别对第三容器、第四容器、第五容器、第六容器的点按最近邻法则进行排序；然后将第一容器、第二容器清空；再将第三容器与第四容器中的点放入第一容器中，第五容器、第六容器的点放入第二容器中；

[0090] 将正面一个网络的正面点以及反面点分成左、右两部分，是为了在后面配对时将左面点分配给左面的测试针，将右面点分配给右面的测试针，这样使得左面测试针的x坐标始终小于右面测试针的x坐标，从而防止了两针在移动时出现相撞。

[0091] 对第三、四、五、六容器中的点重新进行排序时按照最近邻法则进行排序。起始点分别为各个容器中的第一个点，即x坐标最小的点，然后根据公式d＝max(|xi-xi+1|,|yi-yi+1|)，(xi,yi)为当前点的坐标，(xi+1,yi+1)为其余非有序点的坐标，计算其余所有非有序点到当前点的距离，取其中距离d最小的点排在当前点的后面，然后将该点设置为当前点，重复上面的操作。

[0092] 将第一容器、第二容器清空；再将第三容器与第四容器中的点放入第一容器中，采用先将第三容器的一个点放入第一容器中，再将第四容器的一个点放入第一容器中，依次循环，直到第三容器、第四容器的点都放入了第一容器。采用相同方法将第五容器、第六容器的点放入第二容器中；

[0093] B4、进行开路配对，流程图参见图5；

[0094] B41、当前网络只有正面点或只有反面点时进行单面配对；当前网络既有正面点也有反面点时，进行双面点配对；

[0095] 具体可以通过如下方法判断：如果第一容器的点数为0，说明只有反面点；如果第二容器的点数为0，说明只有正面点；

[0096] B42、当配对的结果为有正、反面各两个点时，保存在第七容器中；当配对的结果为有正、反面各一个点时，保存在第八容器中；当配对的结果为只有正面点时，保存在第九容器中；当配对的结果为只有反面点时，保存在第十容器中；当配对的结果为有两个正面点和一个反面点时，保存在第十一容器中；当配对的结果为有一个正面点和两个反面点时，保存在第十二容器中；

[0097] 在具体实施例中，步骤B41中进行单面点配对时，可按步骤B411～B416进行：

[0098] B411、定义变量i为第一容器的索引，初始值为0即指向第一容器的第一个点，从第一容器的第一个点开始依次向后，当i为0或者i为偶数的时候，配对情况为第一容器中第i结点和第第一容器中第i+1结点，当i>0并且i为奇数的时候，配对情况为第一容器中第i+1结点和第一容器中第i结点；将配对放入第九容器；当索引指向第一容器中倒数第二个点时结束配对，配对完成。

[0099] 同理，当网络只有反面点时反面测试点配对方法同正面测试点配对方法，不同之处在于定义变量i为第二容器的索引，初始值为0即指向第二容器的第一个点，配对结果放入第十容器中。

[0100] 在具体实施中，当前网络既有正面点也有反面点时，进行双面点配对；方法如下：

[0101] B412、当正面点数大于1，反面点数为1时,配对方法为：将反面点作为“公共点”，分别从第三容器、第四容器中取出第一个点，与反面点进行配对，结果放入第十一容器中；重复以上步骤直到第三容器，第四容器中的最后一个点；若其中一个容器比另一个容器多一个点，则将多一个点的那个容器的最后一个点与反面点进行配对，配对结果放入第八容器中；

[0102] B413、当反面点数大于1，正面点数为1时,配对方法为：将正面点作为“公共点”，分别从第五、第六容器中取出第一个点，与正面点配对，结果放入第十二容器中；重复以上步骤直到第五容器，第六容器中的最后一个点；若其中一个容器比另一个容器多一个点，则将多一个点的那个容器的最后一个点与正面点进行配对，配对结果放入第八容器中；

[0103] B414、当正、反面的点数都大于1，并且 时，配对方法为：

[0104] ①、定义变量j为第二、三、四容器的索引，初始值为0即指向第二、三、四容器的第一个点；

[0105] ②、当j≤反面点数-2并且j为偶数的时候，按照第三容器第j点、第四容器第j点、第二容器第j点、第二容器第j+1点的顺序进行配对，配对为两个正面点和两个反面点，放入第七容器中；

[0106] 当j≤反面点数-2并且j为奇数的时候，按照第三容器第j点、第四容器第j点、第二容器第j+1点、第二容器第j点的顺序进行配对，配对为两个正面点和两个反面点，放入第七容器中；

[0107] 当j＞反面点数-2时，按照第三容器第j点、第四容器第j点、第二容器最后一个点的顺序进行配对，配对结果为两个正面点和一个反面点，放入第十一容器中。

[0108] 重复上述步骤直到

[0109] ③、当 也就是最后一次配对时，如果正面点数为奇数，配对结果为第四容器的最后一个点、第二容器的最后一个点，即一个正面点和一个反面点，保存到第八容器中；如果正面点数为偶数，配对结果为第三容器的最后一个点、第四容器的最后一个点、第二容器的最后一个点，即两个正面点和一个反面点，放入第十一容器中。

[0110] B415、进行双面点配对时，当正反面点数都大于1，并且当时，配对方法如下：

[0111] ①定义变量k为第一、五、六容器的索引，初始值为0即指向第一、五、六容器的第一个点；

[0112] ②、当k≤正面点数-2，并且k为偶数的时候，按照第一容器第k点、第一容器第k+1、第五容器第k点、第六容器第k点的顺序进行配对，配对为配对为两个正面点和两个反面点，放入第七容器中；

[0113] 当k≤正面点数-2并且k为奇数的时候，按照第一容器第k+1点、第一容器第k点、第五容器第k点、第六容器第k点的顺序进行配对，配对为配对为两个正面点和两个反面点，放入第七容器中；

[0114] 当k＞正面点数-2时，按照第一容器最后一个点、第五容器第k点、第六容器第k点的顺序进行配对，配对为两个正面点和一个反面点，放入第十一容器中；

[0115] 重复上述步骤直到

[0116] ③、当 也就是最后一次配对时，如果反面点数为奇数，将第一容器最后一个点、第六容器最后一个点，配对为一个正面点和一个反面点，反应保存到第八容器中；如果反面点数为偶数，将第一容器最后一个点、第五容器最后一个点、第六容器最后一个点，配对为两个正面点和一个反面点，放入第十一容器中；

[0117] 其中， 条件是依据开路测试的原理而设计的。因为开路测试的任务是依次检测每个网络中的点是否都联通，换句话说每个网络中的任意两点都应该是导通的，同一个网络中不应该存在开路情况。而飞针测试机的四根针一次能检测6组导通关系。因此依照开路测试的原理，为了使每个网络的配对尽可能地少，当所测PCB板正反两面都有测试点时，若 时，假设正面点数为12，反面点数为6，那么按
照B413的方法配对形式为图9所示。

[0118] 从图中可以看出，对于反面点是将其串联起来形成一串，而正面点是按x坐标的大小，将x坐标小的点放在第一根针位置上，x坐标大的点放在第二根针位置上。利用飞针测试机的四根测试针一次能够检测6组导通关系的原理。将反面点串联，若反面点导通，若与之连接的正面点也导通，则整个网络的所有点都导通。

[0119] 同理，设计 为了将正面点串联起来，将反面点x坐标小的点放在第三根针位置上，将反面点x坐标大的点放在第四根针位置上，若正面的点全部导通，则若反面的所有点都与正面的点导通则整个网络导通。

[0120] B416、当网络只有一个正面点和一个反面点时，则将这两个点配对放入第八容器中。

[0121] B5、当前网络处理完成后清空第一、第二、第三、第四、第五、第六容器，并将反面可测试点容器中的所有第二容器中的点删除,正面可测试点容器中的所有第一容器中的点删除；

[0122] 第一、二、三、四、五、六容器保存当前进行处理的网络的信息，当前网络处理完成后，需要清空它们保存的信息，以便处理新的网络时使用。

[0123] 第二容器保存当前进行配对网络的反面点，反面可测试点容器内保存所有反面点，通过反面可测试点容器是否为空来判定所有双面网络以及反面网络已经配对完成，若反面可测试点容器为空则处理剩下的正面网络，因此每当配对完双面网络或者反面网络后都要对相应的反面可测试点容器内的点进行清除。同理每次配对完双面网络或者正面网络后也要对相应的正面可测试点容器内的点进行清除。

[0124] B6、判断正、反面可测试点容器是否都为空，若不为空，重复B2、B3、B4、B5步骤；若为空执行B7；

[0125] B7、为了进一步缩短行数，进行配对合并，可将第八容器中的配对相互合并，将第九容器与第十容器的配对合并，合并后放入第十三容器中。具体流程参见图7；

[0126] 在配对完成后下一步操作是合并配对点。因为第九容器中保存的配对只有正面两个点，第十容器中保存的配对只有反面两个点，所以将第九容器与第十容器合并为一行，而第八容器中的配对为一个正面点和一个反面点，将第八容器中的点合并为一行。将以上合并的行都保存至第十三容器中。为形象的说明配对原理，下面示例说明。conti.lst文件数据行由四个点的信息组成，左边两个为PCB板正面点，右边两个为PCB板反面的点，若某个位置为空则为0h 0y 0表示该位置没有测试点，飞针测试机对应该位置的针脚此时保持不动，cont i.lst文件如图10所示。

[0127] 第八容器中的配对为一个正面点、一个反面点，为使得文件行数最少应该将第八容器中的配对互相合并，使其填满一行不留空位，合并时应注意为防止出现撞针，从左至右第一个点的x坐标应小于第二个点的x坐标，第三个点的x坐标应小于第四个点的x坐标。假设第八容器中有两个配对64c 1111y 1111 64s 2222y 2222与54c 1112y 1112 54s 2223y 2223那么合并成一行后应为:

[0128] 64c 1111y 1111 54c 1112y 1112 64s 2222y 2222 54s 2223y 2223同理第九第十容器中的配对合并也要防止出现撞针。

[0129] 在具体实施例中，可按如下B71～B78方法进行配对合并：

[0130] B71、取出第八容器中的两个配对合并成行保存至第十三容器中。

[0131] B72、取出第七容器中的一个配对成行保存至第十三容器中。

[0132] B73、判断第九容器是否为空，当第九容器不为空时判断第十容器是否为空，若第十容器也不为空，则分别从第九容器、第十容器中取出一配对合并成行后放入第十三容器中。

[0133] B74、若第九容器不为空，第十容器为空，则将第九容器中配对取出，合成一行后放入第十三容器中。

[0134] B75、若第九容器为空，第十容器不为空，则将第十容器中的配对取出，合成一行后放入第十三容器中。

[0135] B76、取出第十一容器中的配对成行后保存至第十三容器中。

[0136] B77、取出第十二容器中的配对成行后保存至第十三容器中。

[0137] B78、重复B71、B72、B73、B74、B75、B76、B77直到合并完成；

[0138] C、开路优化，具体流程见图8。在具体实施例中可按步骤C1～C6进行：

[0139] C1、初始化链表，读取第十三容器中的第一行的信息，并对链表第一个结点进行初始化，初始化完成后在第十三容器中删除该行；

[0140] C2、定义一个整数型变量min用于保存第十三容器中的行到当前链表最后行的距离最小值，并定义初始值为零；再定义一个整数型变量index，用于保存距离等于min的行在第十三容器中所对应的位置；

[0141] C3将min赋值为0，index赋值为1；

[0142] C4、继续读取第十三容器中的下一行信息，计算它与链表中当前行的距离，若当前距离小于min则将当前距离赋值给min，并将当前位置索引号赋值给index；若当前距离大于min则计算下一个节点；

[0143] C5、判断是否遍历完第十三容器，若遍历完，则将index所指的第十三容器中的行链接到链表的末尾，并删除index所指的第十三容器中的行，然后执行C6；若没遍历完则继续执行C4；

[0144] C6、判断第十三容器是否为空，若为空，表示链表已排好序，最终路径已生成，执行步骤D；若不为空，表示路径还没完全生成，返回执行步骤C3；

[0145] D、生成文件：开路优化完成后，生成新的CONTI.LST文件。

[0146] 飞针测试机可以直接读取CONTI.LST文件进行测试。该文件的格式如图2所示。

[0147] 其中，步骤C4计算该行信息在每个节点处的移动距离采用如下方法：

[0148] C41、计算相邻两行之间的路径距离：例如：

[0149] 用 表示第i行，从左向右第j个点的坐标，dj表示第i行第i+1行从左向右第j个点之间的距离，dj按如下公式计算：

[0150]

[0151] max()为取最大值函数，需要注意的是当结点坐标为零时代表当前此针悬空，不是回到原点；

[0152] 即dj取 两者之中的最大值。

[0153] 定义第i行与第i+1行的移动最终路径长度如下：

[0154] D(i,i+1)＝max(d1,d2,d3,d4)

[0155] 则相邻两行的对应网络的距离计算如下：

[0156] 第一针移动距离:

[0157] 第二针移动距离:

[0158] 第三针移动距离:

[0159] 第四针移动距离:

[0160] 最后，相邻两行的移动距离为四根针移动距离的最大值：

[0161] D(i,i+1)＝max(d1,d2,d3,d4)

[0162] C42、当链表中的n行已经排好顺序，当前要插入的行为第n+1行时，则逐行计算剩余第i行未排序的所有行到已排序的第n行的路径长度Di(n,n+1),选出距离已排序序列第n行路径长度最短的行，作为已排序序列的第n+1行，n,n+1行之间的最短移动距离：

[0163] minDi(n,n+1)＝min(max(d1,d2,d3,d4))

[0164] 当找到距离已排序结点最后一个节点的距离最近的结点后，将其插入到已排序结点的最后面，然后再从第十三容器中读取新一行信息，重复上述操作，直至结束。

[0165] 飞针测试有4根针，正反面各两针，每次测试4个不同点，即文件中的一行，且可以测出4个点之间的六组导通关系。本方法需要正确读取待优化conti.lst文件的信息，生成可以用于4针联动飞针测试机的测试文件，且要求走针路径尽量短。

[0166] 本方法可以描述成如下的优化模型：

[0167] (1)变量定义

[0168] 设经过配对后生成的行为wi其中i∈(1,m)，表示经过配对后共生成m行。

[0169] (2)解空间

[0170] 解空间S为测试路径，解可以表示为{w1,w2,...,wm}，w1,w2,...,wm是所有行的一个排列，表明从文件的第一行w1开始，即四根针从各自的起始位置开始，依次经过w1,w2,...,wm-1，最后到达wm。其中wi与wi+1之间的距离为D(i,i+1)。

[0171] (3)目标函数

[0172] 需要在所有行的所有排列中找到一个排列，使得总路径距离最短

[0173] 令di＝D(i,i+1),即di为第i行到第i+1行的距离，那么路径的总距离最短为：

[0174]

[0175] 求D的值。

[0176] (4)约束条件

[0177] 四根针应该测试完所有的导通关系，不能漏掉，且确保所有的点都检测到。将所有的行用贪婪算法求解，显然求出的解只是众多排列组合可能中的一种，是局部最优解。

[0178] 根据以上的描述，当行数较小的时候，可以验证该结果是否为全局最优解，但是当行数很多时，理论上当行数超过20行用普通计算机求最优解需要一年时间。所以该问题是一个NP完全问题，当数据量超过一定规模时，以当今技术手段无法找到全局最优解。所以，在实际的工程应用中，我们只能找到局部最优解。根据针对PCB飞针测试路径优化来讲，我们主要从两个方面进行优化。一是尽量减少文件的行数，即减少分针移动的次数。二是在行数尽量少的前提下尽量是总的路径距离减少。

[0179] 本发明采用的配对方式，先将各个网络根据正反面的点数，及奇偶情况分类讨论，确保了对每个网络配对时不会出现漏配的情况，而且保证了了不会装针，而且行数少。同时配对后的合并操作进一步减少了文件的行数。

[0180] 使用本发明描述的优化算法对Conti(396超长板)、Conti(2503拼版)和Conti(10035常规)3个lst文件进行开路优化，并同深圳飞翔公司采用的现有测试软件生成的文件进行对比，仿真结果见表1。

[0181] 表1优化算法的仿真结果

[0182]

[0183] 因为PCB板的走线和构造特别复杂，特别是对于多层PCB，还要考虑多针的并行工作，优化起来很有难度。在实际的飞针测试中，发现对于拼版，超长版的优化结果相对于常规板来讲要好很多，因为拼版，超长版的行数一般为常规板的几倍或者几十倍，所以优化效果更加明显。使用本专利提出的开路优化算法对开路测试文件进行优化后，探针所走的最大路径长度相比于原文件，有明显的优化。