個別測試是最優無序群試的條件

Abstract

一個組合上的群試問題是假設n個東西中有最多d個壞物，希望能使用盡可能少的測試數將此d壞物找出。在此篇論文中，我們將研究的問題是，在給定d的值下，決定n值為何？使得我們知道在無序群試中，如果待測東西小於等於n時，用一個一個去測試的方式是最佳的群試方法。我們令N（d）表此最大n值，當d給定下。文中我們將證明在某個條件限制下，N(d)=(d+1)^2 是充要條件，及證明在d = 1,2,3,4且無任何條件限制下， N(d)=(d+1)^2。

The combinatorial group testing problem is, assuming the existence of up to $d$ defectives among $n$ items, to identify the defectives by as few tests as possible. In this thesis, we study the problem what values of $n$, given $d$, individual testing is optimal on nonadaptive group testing. Let $N(d)$ denote the largest $n$ for fixed $d$ that individual testing is optimal. We will show that $N(d)=(d+1)^{2}$ under a prevalent constraint in practical nonadaptive algorithms and prove that $N(d)=(d+1)^{2}$ for $d=1, 2, 3, 4$, without any constraint.