数学物理学报 ›› 2009, Vol. 29 ›› Issue (4): 974-984.

• 论文 • 上一篇    下一篇

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

  

  1. (1.西安电子科技大学 理学院|西安 250101, 2.山东建筑大学 理学院, 济南 250101)
  • 收稿日期:2006-10-08 修回日期:2008-04-06 出版日期:2009-08-25 发布日期:2009-08-25
  • 基金资助:

    国家自然科学基金(60574075)资助

On the Approximate Control Criteria for Combinatorial Group Testing Procedure

  1. (1.Department of Mathematics Science, Xidian University, Xian 710071, 2.School of Sciences, Shandong Jianzhu University, Jinan 250101)
  • Received:2006-10-08 Revised:2008-04-06 Online:2009-08-25 Published:2009-08-25
  • Supported by:

    国家自然科学基金(60574075)资助

摘要:

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

关键词: 伪硬币, 标准硬币, 分组测试, 天平, 近似控制标准

Abstract:

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.

Key words: Defective coins, Standard coins, Group testing, Balances, Proximate control criteria

中图分类号: 

  • 68R05