样本参与组测试数有上限约束的组合群试问题研究

Combinatorial group testing problem considers how to choose a series of subsets for testing from a sample set, where each test result indicates whether a subset contains at least one defective item or not. The goal is to identify all the defective items in the sample set using as few tests as possible. In this project, we plan to study the design of testing strategies for three different scenarios (to identify all the defective items, to identify one defective item, and to identify a given number of good items) under the combinatorial group testing model, under the condition that each item is allowed to participate in a constrained number of testing groups. The constraint on the number of participating groups for each item is relevant in practice, for typical applications of combinatorial group testing problem such as blood testing. Moreover, studying combinatorial group testing problems with the above constraint provides us a way to study, when the number of defective items is unknown in advance, group testing problems with constrained number of positive responses. The study of group testing problems with the latter type constraint is for some applications, e.g., leak testing on sealed radioactive sources, in which a test involving a defective item may cause harm to the personnel performing the test or to the testing device. The research in this project aims to design testing strategies with both good theoretical guarantee and desirable practical performance, to solve the above problems, and to further enrich the research on combinatorial group testing problems.

组合群试问题考虑如何选择一个样本集的一系列子集进行测试，对每个子集的测试结果显示该子集是否至少含有一个有缺陷的样本。问题目标是通过尽可能少的测试来识别出所有的缺陷样本。本项目拟研究在样本能够参与的组测试数有上限约束条件下,三个不同情形下的组合群试问题（包括识别出全部的缺陷样本，识别出一个缺陷样本，以及识别出给定数量的好样本）的测试策略设计。样本参与组测试数有上限这一约束，在验血等组合群试问题的典型应用中具有实际意义。另外，对带有上述约束的组合群试问题的研究，也给出了缺陷样本数未知情况下，阳性测试结果数有上限的群试问题的一个研究思路。对后一类群试问题的研究是考虑在一些应用中，例如对密封的放射性物质进行泄露检测，对缺陷样本的测试可能会对测试人员或仪器造成一定程度的危害。本项目旨在设计具有好的理论分析结果和实际执行效果的测试策略，来分别解决上述问题，以进一步丰富关于组合群试问题的研究。

群试问题考虑如何选择一个样本集的一系列子集进行测试，测试结果显示每个子集是否至少包含一个有缺陷的样本，使得通过尽可能少的测试确定出样本集里所有的缺陷样本。在实际应用中，样本集里缺陷样本的个数通常是未知的，同时每个样本能够参与的测试数通常有上限约束。我们研究了输入集合中缺陷样本个数未知情况下样本参与测试数有上限约束的组合群试问题，给出了一个新的确定性递归测试策略，同时证明了对于该问题任意确定性测试策略需要测试数的一个下界。在样本参与测试数上限为常数的情况下，我们给出的测试策略需要的测试数是渐进最优的。该问题本身具有理论上的研究意义以及包括血样检验等实际应用意义，同时对该问题的研究还为缺陷样本个数未知情况下阳性测试结果数有上限约束的组合群试问题的研究提供了一个新的思路。阳性测试结果数有上限约束的组合群试问题的应用包括放射性或有毒副作用物质的泄露检测等，在这些应用中测试中的缺陷样本可能会对测试人员或设备造成一定程度的损伤。我们同时研究了当输入集合中只包含一个缺陷样本同时阳性结果测试数不超过给定上限时，该问题随机测试策略期望测试数的最小值，给出了最优期望测试数精确的上下界估计。我们研究的另一个问题是识别输入集合中的一部分好样本，使得识别出的好样本数量占样本总数比例不低于一个预先给定值这一群试问题的变形。对于输入集合中缺陷样本数未知的情形，我们给出了该问题的一类测试策略，当该预先给定的比例值趋近于1时这类测试策略所需测试数是渐进最优的。同时我们证明了对于该问题任意确定性测试策略需要测试数的一个下界。最后，对于缺陷样本个数未知情况下识别出集合中所有缺陷样本这一组合群试领域的核心问题，在之前最优测试算法的基础上，通过改进所选测试子集大小的设定方式，以及创造性地设计了一个对于包含缺陷样本子集的进一步划分方法，我们给出了该问题的一个进一步改进的算法，使得算法在最坏情形下的测试数进一步降低。