基于启发式图搜索的最小测点集优选新算法

New minimum test point set selection algorithm based on heuristic graph search

模拟故障字典的测点选择问题是目前的一个研究热点。本文将这一问题转化为启发式图搜索问题,测点选择过程就变成了图节点的扩展过程。运用信息理论和M进制编码规则,首先给出了启发函数的计算方法,推导出图节点的构造方法和扩展规则,然后在此基础上给出了用于测试节点优选的启发式图搜索算法,最后进行了分析实验。实验结果表明本算法既克服了局部寻优方法不能找到全局最小测点集的缺点,又能显著降低传统穷举搜索算法的时间复杂度和空间复杂度。

The problem of test point set selection for analog fault dictionary has attracted a great deal of interest recently. This problem is formulated as a heuristic depth-first graph search problem. Then, the test point selection progress becomes a graph node expanding progress. Based on information theory and M-ary code rule, the method of calculating heuristic evaluation function is given, the methods of constructing graph node and expanding the node are deduced firstly. Then a new heuristic graph search algorithm is given. Statistical experiments were carried out; experiment results show that this new algorithm can not only find the global minimum test point set but also decrease the time and space complexities of traditional search algorithms dramatically.