论文标题
最佳的多阶段组测试算法3次缺陷
Optimal Multistage Group Testing Algorithm for 3 Defectives
论文作者
论文摘要
小组测试是一个众所周知的搜索问题，它包括通过对正确选择的样本子集进行测试来检测一组$ t $样本的有缺陷成员。在经典组测试中，目标是通过在最坏情况下使用最小可能的测试数量来找到所有有缺陷的元素。在这项工作中，考虑了多阶段的测试问题。我们的目标是构建一个多阶段搜索过程，其渐近数与最佳自适应算法的测试数量相同。我们提出了一种设计多阶段算法的新方法，该方法使我们能够构建一种5阶段算法，用于查找3个缺陷，其中最佳数字$ 3 \ log_2t（1+o（1+o（1））$。
Group testing is a well-known search problem that consists in detecting of $s$ defective members of a set of $t$ samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, a multistage group testing problem is considered. Our goal is to construct a multistage search procedure, having asymptotically the same number of tests as the optimal adaptive algorithm. We propose a new approach to designing multistage algorithms, which allows us to construct a 5-stage algorithm for finding 3 defectives with the optimal number $3\log_2t(1+o(1))$ of tests.
