基于广义AO算法的测试序列问题研究

Research on Test Sequencing Problem Based on Generalized AO Algorithm

测试序列问题的目标是用最小的期望测试费用找到最佳测试序列。提出了一种广义AO*算法解决了电子设备的测试序列问题。对传统的AND/OR图进行扩展得到一种广义的AND/OR图,它不仅能够提高AND/OR图的表达能力而且能够实现推理操作符与问题之间的多对多关系;描述了广义AO*算法的步骤并且分析了该算法的计算复杂度。通过实例说明广义AO*算法不仅可有效减少计算复杂度和平均测试代价,而且生成的故障诊断策略能快速、有效的指导维修人员定位故障以减少维修代价。

The objective of the test sequencing problem is to develop an optimal test sequence with the minimal expected test cost. For solving the problem of the electronic equipment, a generalized AO algorithm was presented. The traditional AND/OR graph was extended to the generalized AND/OR graph, which improves the expressive ability of AND/OR graph and achieves the many-to-many relation between reasoning operator and unsolved problems; the steps of the generalized AO algorithm were described and its complexity was analyzed. The calculated results by an example show that the generalized AO algorithm can effectively decrease calculational complexity and average test cost, and the generated fault diagnosis strategy can quickly guide maintenance man to locate the fault to reduce maintenance costs.