组合的分组测试算法的近似控制标准

On the Approximate Control Criteria for Combinatorial Group Testing Procedure

对于给定的一个集合,分组测试问题是通过一系列的测试去确定这个集合的一个子集.在文中,作者首先运用动态规划的理论与方法,建立了一个近似控制标准,目的是对分组测试算法的构建过程进行有效控制,使所构建的算法达到最优.其次,应用该近似控制标准研究了在n个硬币集合中确定一个伪硬币的最小平均测试数的问题.文中所涉及的近似控制问题,给出了在一个给定集合中去确定这个集合的一个子集的最优分组测试算法,该最优分组测试算法是在平均测试步骤最少意义下的最优分组测试算法.

The group testing problem for a given set is to determine a subset of the set by a series of tests. In this paper, firstly, the authors use the theory and method of dynamic programming to establish a proximate dominating criterion for controlling group testing procedures. Establishing the group testing procedure is optimal through the control. Secondly, the authors consider the problem of ascertaining the minimum average number of tests which suffice to determine one defective coin in a set of n coins by applying the proximate control criterion. In particular, this paper is concerned with proximate control problem on a group testing procedure, in which an optimal procedure for culling out the one subset of a given set is obtained. The desired procedure is optimal in the sense of minimizing the average number of steps.