开关矩阵作为信号传递的枢纽，在自动测试设备内部扮演着极其重要的角色。当信号源节点与目标节点之间距离最短时，信号才能最有效地传输。基于开关矩阵的物理模型，结合图论知识，构造了开关矩阵的数学模型。针对通路继电器最少、系统可靠性最高2 种情形，把路径最短问题抽象成无权图和有权图的最短路径搜索问题，分别采用广度优先搜索（BFS）算法和Dijkstra 算法进行研究，并提出改进型算法。通过具体实例，建立模型并应用改进算法予以实现。改进算法应用于ATE 通用适配器的开发研制和自动测试设备软件平台的设计，可实现最佳测试路径的快速自动搜索，具有工程实践价值。
As a signal transfer hub, switch matrix plays an extremely important role in the automatic test equipment (ATE). When the distance between the source node and destination node is the shortest, signals can be transmitted in a most efficient way. First, a physical model of switch matrix is presented. Then a mathematical model is constructed by using graph theory. In view of the least relay and highest reliability, the problem is considered as a shortest path search in un-weighted graph and weighted graph. These two graphs arestudied by BFS algorithm and Dijkstra algorithm, and the improvedalgorithm is put forward. An actual example shows how to build the model and find the optimum path. The improved algorithm could realize rapid automatic searchfor the optimum path, thus has potential applicationsin development of general adapters and design of software platform in ATE.
[1] Sun B J, Qin H L, Shen S T. An automatic design technique for hardware system of ATS[C]. Autotestcon 2006 IEEE, Anaheim CA, Sept 18-21, 2006.
[2] Burden J, Curry P A, Roby D, et al. Introduction to the nest generation automatic test system(NGATS) [C]. Autotestcon 2005 IEEE, Anaheim CA, Sept 26-29, 2005.
[3] Lemon R, Coulter B. Interface test adapter development & maintenance using a continuity/insulation automatic test station in large scale test systems[C]. Autotestcon 2009 IEEE, Anaheim CA, Sept 14-17, 2009.
[4] Ross W A. The impact of next generation test technology on aviation maintenance[C]. Autotestcon 2003 IEEE, Anaheim CA, Sept 22-25, 2003.
[5] Blanchard B S. Logistics. Engineering and management[M]. New York: Prentice Hall, 1992.
[6] Orlet J L, Murdock G L. NxTest augments legacy military ATE[J]. IEEE Aerospace and Electronic Systems Magazine, 2002, 17(11): 17-20.
[7] 赵劲松, 孟晓风. 一种ATE开关最短路径搜索算法[J]. 电子测量与仪 器学报, 2006, 20(3): 33-36. Zhao Jinsong, Meng Xiaofeng. A kind of BFS to search the optimum path of ATE switches[J]. Journal of Electronic Measurement and Instrument, 2006, 20(3): 33-36.
[8] 龚劬. 图论与网络最优化算法[M]. 重庆: 重庆大学出版社, 2009. Gong Qu. Optimization algorithms for network and graph[M]. Chongqing: Chongqing University Press, 2009.
[9] 赵瑞贤, 孟晓风, 王国华. 通用ATE开关资源测试路径模型及应用[J]. 北京航空航天大学学报:自然科学版, 2006, 32(2): 181-185. Zhao Ruixian, Meng Xiaofeng, Wang Guohua. General-unility testing path model of switches for ATE and application[J]. Journal of Beijing University of Aeronautics and Astronautics: Natural Science Edition, 2006, 32(2): 181-185.
[10] 王怡苹, 李文海, 文天柱. 面向信号测试的路径搜索算法研究[J]. 仪 器仪表学报, 2013, 34(7): 1650-1658. Wang Yiping, Li Wenhai, Wen Tianzhu. Research on path search algorithm for signal-oriented test[J]. Chinese Journal of Scientific Instrument, 2013, 34(7): 1650-1658.
[11] 张玮, 沈士团, 陈星. 自动测试设备多开关模型的构造方法及其实现[J]. 遥测遥控, 2003, 24(1): 25-29. Zhang Wei, Shen Shituan, Chen Xing. A kind of modeling method and implementation for multiple switch modules in ATS[J]. Journal of Telemetry Tracking and Command, 2003, 24(1): 25-29.
[12] 张海良, 苏岐芳, 林荣斐. 图论基础[M]. 北京: 清华大学出版社, 2011. Zhang Hailiang, Su Qifang, Lin Rongfei. Graph theory[M]. Beijing: Tsinghua University Press, 2011.
[13] 卢启衡, 冯晓红. 基于宽度优先搜索的路径生成算法[J]. 现代计算 机, 2006(12): 87-89. Lu Qiheng, Feng Xiaohong. Search path building algorithm based on breadth-first search[J]. Modern Computer, 2006(12): 87-89.
[14] 高利民, 李文慧, 孙慧. 双向广度搜索算法在联锁进路自动生成中的 应用[J]. 铁路计算机应用, 2007, 16(5): 43-45. Gao Limin, Li Wenhui, Sun Hui. Application of bidirectionalspan searched algorithm to automatic generating of interlocked path[J]. Railway Computer Application, 2007, 16(5): 43-45.
[15] 王国华, 杨中亮, 陈妮亚. ATE开关矩阵动态路径搜索算法[J]. 北京 航空航天大学学报: 自然科学版, 2010, 36(1): 39-42. Wang Guohua, Yang Zhongliang, Chen Niya. Dynamic path searching method for ATE switch matrix[J]. Journal of Beijing University of Aeronautics and Astronautics: Natural Science Edition, 2010, 36(1): 39-42.
[16] 王华. 基于邻接点算法的Dijkstra优化研究[J]. 计算机与数字工程, 2013(4): 518-520. Wang Hua. Improved Dijkstra algorithm based on the adjacent point in shortest path[J]. Computer & Digital Engineering, 2013(4): 518-520.
