1、需求背景及原因：

        当今电子产品高性能计算能力愈来愈强，然而同时，却日趋轻、薄和小型便携化，推动着 IC 封装基板朝着更高密度互连方向发展。IC 封装基板 具有以下典型特征：超高孔群密度分布（约每平方英寸2000孔，孔径0.1mm 左右）；线宽/线距 L/S 降低到15微米以内水平，对制程良率带来巨大挑战。使用电测方式，对基板开路和短路不良进行检测，是当前主流的品控手段，可以显著降低流到后续制程或终端消费者带来的数十倍甚至百倍损失。本项目考虑研发8 头双面卧式飞针测试机，对 IC 封装基板开、短路检测，基板上方和下方分别分布有 4 个测试探针，每个测试探针由 XYZ 三轴 高速直线电机独立驱动，可以在基板平面和高度方向作快速移动。相对于高精密治具测试机，飞针测试机具有极高的测试柔性，显著降低小批量基板测试所需的高昂治具成本。

2、具体需求：

        已知基板正反面均存在有测试点集合，根据这些测试点相互之间的导通关系将这些测试点分为很多个“子集”，每个“子集”内部的任意两点之间都应该导通，对应的测试方法即为开路测试；任意两个不同“子集"之间都应该绝缘，对应的测试方法即为短路测试。业界称这样的“子集” 称为同一个网络。针对以上配置飞针测试机台，给定输入测试文件，开、短路测试需要完成所有网络内部所有测试点的“导通测试”和不同网络之间的“绝缘测试”，实际上存在任意多测试规划方案，

3、预期技术目标:

        公司要找出相对较优的测试方案，即：测试次数要少、不同测试探针综合移动距离要尽量短。 这是个组合优化问题，获得其精确最优解，是典型的 NP 难题。其中也涉及特定应用场景下的欧式空间 TSP 问题。公司的技术需求就是要解决方案方针对以上应用情景，研究获得近似最优测试规划算法，使得公司的飞针测试机台具有极佳的测试效率。