二装置并行搜索分解数为2的两个坏硬币平衡模型的统一测试过程

Unified search procedure with two devices on equilibrium models of two-counterfeit-coin problem

如何迅捷地从某类物品中搜索出具有给定特征的物品是一个有广泛实际背景的问题 .描述这一类问题的数学模型中 ,2台装置并行搜索 2个坏硬币的分解数为 2的 6个平衡模型Mi(i =1 ,2 ,… ,6 )最为常见 .然而至今为止 ,这 6个模型中仅有一个模型M1 的测试过程已给出 .本文采用二分测试树及深度优先算法 ,给出了这 6个平衡模型的统一测试过程t,使当k为奇数时 ,tk/nk =1 ,当k为偶数时tk/nk >0 .93 .这里tk 表示测试过程t在k次测试中所能鉴别的最大硬币数目 ,nk =maxtk.从而完全、统一地解决了分解数为 2之平衡模型的测试问题 .本文的结果可以直接应用于次品搜索。

How to quickly select objects with certain special character among plenty of objects is a problem in various practical situations. Amid mathematical models of these problems, six equilibrium models M i,i=1,2,…,6 with resolution number 2 for Two-Counterfeit-Coin problem are popular. However, only one model M 1’ test procedure has been given so far. In this paper, using both depth-first search algorithm and binary testing tree an unified search procedure t on equilibrium models M i,i=1,2,…,6 is established. t k/n k=1 when k is odd whilst t k/n k>0.93 when k is even, where t k is the maximum number of coins identifiable in k tests by using procedure t and n k=maxt k. Thus the testing problem of all the equilibrium models with resolution number 2 is resolved uniformly. This method can be applied directly to various practical problems such as defective goods detecting, system testing and so on.