缺陷元素个数未知情况下的组合群试策略研究

群试问题考虑如何选择一个样本集的一系列子集进行测试，测试结果显示每个子集是否至少包含一个有缺陷的元素，使得通过尽可能少的测试确定出样本集里所有的缺陷元素。在实际应用中，样本集里缺陷元素的个数通常是未知的，估计缺陷元素个数是另一个重要的问题。后者目前已有的测试策略需要的测试数依赖于样本集的总大小，而且是对缺陷元素个数近似估计。本项目拟研究不同的随机测试策略分别来返回缺陷元素个数的准确值和近似估计值，所需的测试数依赖于样本集里缺陷元素个数而不依赖于样本集的总大小。在缺陷元素占样本集比例很小的许多实际应用中，研究结果将显著减少需要的测试数量。同时填补了之前关于确定缺陷元素确切个数的随机测试策略研究上的空白。对于确定所有缺陷元素的问题，本项目拟研究首先近似估计样本集里缺陷元素的个数，然后基于该估计值选择子集进行测试来确定所有的缺陷元素的新方法，研究结果十分有望改进该问题目前已知的最优测试策略。

群试问题考虑如何选择一个样本集的一系列子集进行测试，测试结果显示每个子集是否至少包含一个有缺陷的元素，使得通过尽可能少的测试确定出样本集里所有的缺陷元素。在实际应用中，样本集里缺陷元素的个数通常是未知的，估计缺陷元素个数是另一个重要的问题。对于估计样本集中缺陷元素个数这个问题，我们给出了两个随机测试算法分别得到缺陷元素个数的准确值和近似估计值。这两个算法所需的测试数依赖于样本集里缺陷元素个数而不依赖于样本集的总大小。在缺陷元素占样本集比例很小的许多实际应用中，我们的研究结果显著减少了需要的测试数。对于确定所有的缺陷元素这一问题，我们主要的研究成果分为两部分。第一部分是给出了一个首先采用随机测试算法近似估计缺陷元素的个数，然后基于该估计值适当地选择子集进行测试来确定所有缺陷元素的随机群试算法。在大多数实际应用中的问题都满足的参数条件下，我们提出的算法所需测试数的上界渐近小于之前最好的研究结果。第二部分是直接通过选择样本集的子集进行测试来找出所有的缺陷元素的确定性群试算法的设计。这部分包括两个主要的研究结果。第一个研究结果是一个基于“锯齿形”（zig-zag）搜索方法的确定性群试算法。同样，在大多数实际应用中的问题都满足的参数条件下，我们提出的算法所需测试数的上界渐近小于之前最好的研究结果。该“锯齿形”搜索方法在之前的研究中没有提出过，该方法的提出及其理论分析结果是确定性群试算法设计中一个有意义的进展。第二个研究工作是对该问题的一个拓展，即考虑同时使得测试次数和测试阶段数都尽可能小的群试算法。在实际应用中，测试次数对应于所需要的费用，而测试阶段数对应于所需要的最短时间，因此在实际问题中测试阶段数也非常重要。之前尚没有对该类问题在缺陷元素个数未知情况下的研究。我们给出了一个新的确定性群试算法并给出了其所需测试数的理论分析，同时计算实验表明我们给出的算法所需的平均测试数和平均阶段数都优于之前已有的算法。