假設在 \(1,000\) 人的群體中，恰好隱藏著 \(1\) 名某種傳染病的陽性感染者。為了以 \(100\%\) 的準確率找出這名陽性個體，至少需要進行多少次檢測？

直覺告訴我們需要逐一檢測全部 \(1,000\) 人，即進行 \(1,000\) 次檢測。然而，數學與資訊理論給出了截然不同的答案：如果我們允許將多人的生物檢體混合（Pooling）在一起檢測「混合檢體中是否至少含有一名陽性個體」，那麼採用分步縮小的自適應策略（Adaptive Group Testing）只需區區 \(10\) 次檢測；更令人驚嘆的是，即便在檢測開始前就完全固定所有混合方案、將全部檢測在同一批次平行完成（非自適應群測試，Non-Adaptive Group Testing），也僅僅需要幾十次檢測就能一步到位地精準鎖定陽性感染者。

這一看似魔術的方法，正是橫跨數理統計、離散數學、編碼理論與資訊理論的群測試（Group Testing，又稱分組檢測或池化檢驗）與組合搜尋（Combinatorial Search）理論。本文將從1943年羅伯特·多夫曼（Robert Dorfman）的二戰奠基論文出發，嚴格推導香農資訊理論下界，對比「12枚假幣天平稱重問題」與黃光明（Frank K. Hwang）廣義二分搜尋，剖析考茨與辛格爾頓（Kautz & Singleton）提出的析取矩陣（Disjunct Matrix / 疊加碼）與有限體里德-所羅門（Reed-Solomon）多項式設計，並揭示其與現代壓縮感知（Compressed Sensing）、多址通訊碰撞消解以及 COVID-19 高通量 P-BEST 核酸混檢之間的深刻數學對偶性。

1. 1943年的戰時突破：多夫曼二階段池化檢驗法（Dorfman Pooling）

1.1 二戰徵兵篩檢與瓦氏血液檢測瓶頸

群測試的數學史始於1943年12月。當時美國統計學家羅伯特·多夫曼（Robert Dorfman）在《數理統計年鑑》（The Annals of Mathematical Statistics）上發表了一篇僅6頁卻影響深遠的論文——“The Detection of Defective Members of Large Populations”（大規模母體中缺陷成員的檢測）。

第二次世界大戰期間，美國陸軍需要對數百萬應徵入伍的新兵進行梅毒（Syphilis）篩檢。當時的標準檢測手段是瓦氏反應血液檢測（Wassermann test），不僅試劑昂貴、操作繁瑣，而且在新兵群體中梅毒的真實盛行率 \(p\) 極低（通常在 \(p \approx 0.01\) 到 \(p \approx 0.001\) 之間）。這意味著如果對每個人單獨驗血，超過 \(99\%\) 的檢測資源都耗費在「確認健康人為陰性」這一重複勞動上。

多夫曼提出了一個極具洞察力的兩階段方案：不再逐一檢測，而是將 \(N\) 名新兵按每組 \(k\) 人劃分為若干個不相交的檢體池（Pool），將同組 \(k\) 人的血清各取一部分混合在一支試管中進行檢測。

1.2 多夫曼二階段演算法流程

假設母體總人數為 \(N\)，每個個體獨立地以機率 \(p\) 呈陽性（\(1\)），以機率 \(q = 1 - p\) 呈陰性（\(0\)）。多夫曼二階段混檢法對每個大小為 \(k\) 的檢體池執行以下兩步：

1. 第一階段（混合池初篩）：將池內 \(k\) 個檢體混合，僅進行 \(1\) 次檢測。
   • 若混合池呈陰性（Negative）（機率為 \((1 - p)^k\)）：說明這 \(k\) 個人全部為陰性！僅用 \(1\) 次檢測就排除了 \(k\) 個人的感染可能，該組檢測直接結束。
   • 若混合池呈陽性（Positive）（機率為 \(1 - (1 - p)^k\)）：說明這 \(k\) 人中至少有 \(1\) 人為陽性，進入第二階段。
2. 第二階段（個體複核）：對呈陽性的混合池內的全部 \(k\) 個原始留存檢體逐一進行單獨檢測（共消耗 \(1 + k\) 次檢測），從而精確定位所有陽性個體。

  flowchart TD
    A["將 N 個檢體劃分為大小為 k 的不相交檢體池"] --> B["第一階段：將 k 個檢體混合進行 1 次檢測"]
    B --> C{"混合池檢測結果如何？"}
    C -- "陰性：機率 (1 - p)^k" --> D["池內 k 人全部確認為陰性！<br/>（累計消耗檢測次數：1 次）"]
    C -- "陽性：機率 1 - (1 - p)^k" --> E["第二階段：對池內 k 人逐一單獨複檢<br/>（累計消耗檢測次數：1 + k 次）"]

1.3 期望檢測次數推導與最佳池大小 \(k^*\) 的解析解

如何選擇每組的人數 \(k\) 才能使總期望檢測次數最少？若 \(k\) 太小，第一階段的混合池數量過多；若 \(k\) 太大，幾乎每個混合池都會包含至少一名陽性感染者而呈陽性，導致幾乎所有人都要進行第二階段複檢。

對於一個大小為 \(k\) 的檢體池，其消耗的檢測次數 \(T_{\text{pool}}\) 的數學期望值為：

將其除以池大小 \(k\)，即得到人均期望檢測次數 \(f(k) = \frac{\mathbb{E}[T]}{N}\)（當 \(k \ge 2\) 時）：

當盛行率 \(p \ll 1\)（且 \(kp \ll 1\)）時，利用一階泰勒展開（二項近似）\((1 - p)^k \approx 1 - kp\)，上式簡化為：

利用算術幾何平均不等式（AM-GM 不等式）或對 \(k\) 求導並令導數為零，立即求得最佳池大小 \(k^*\) 與最小人均檢測次數：

讓我們代入具體數值感受這一平方根法則的威力：

• 當盛行率 \(p = 0.01\)（\(1\%\) 陽性率）時：最佳池大小 \(k^* \approx \frac{1}{\sqrt{0.01}} = 10\) 人（精確離散最佳解為 \(k^* = 11\)）。此時人均檢測次數僅為 \(\frac{\mathbb{E}[T]}{N} \approx 2\sqrt{0.01} = 0.20\) 次（精確值為 \(0.1956\) 次）。這意味著篩檢 \(1,000\) 人只需要約 \(200\) 次（精確為 \(196\) 次）檢測，直接節省了 \(80\%\) 的檢測量！
• 當盛行率 \(p = 0.0001\)（萬分之一陽性率）時：最佳池大小 \(k^* \approx \frac{1}{\sqrt{0.0001}} = 100\) 人，人均檢測次數降至 \(\frac{\mathbb{E}[T]}{N} \approx 2\sqrt{0.0001} = 0.02\) 次。篩檢 \(10,000\) 人僅需 \(200\) 次檢測，消除了整整 \(98\%\) 的檢測成本！

2. 香農資訊理論下界：檢測次數最少能壓縮到多少？

多夫曼方法將人均檢測數從 \(1\) 降到了 \(2\sqrt{p}\)（當總陽性人數為 \(d = Np\) 時，總檢測數為 \(2\sqrt{Nd}\)）。但如果允許使用任意多階段或任意複雜的組合設計，物理定律所允許的絕對最少檢測次數是多少？

1. 組合模型下的計數下界（Counting Bound）： 假設 \(N\) 個檢體中恰好有 \(d\) 個陽性檢體（未知陽性集合 \(S \subset [N], |S| = d\)）。共有 \(\binom{N}{d}\) 種可能的陽性集合。每次二元檢測的輸出僅為 \(\{0, 1\}\)（陰性或陽性），最多提供 \(1\) 位元（bit）的香農資訊量。經過 \(T\) 次檢測後，結果向量 \(\mathbf{y} \in \{0, 1\}^T\) 最多有 \(2^T\) 種可能取值。由鴿籠原理，要唯一區分所有 \(\binom{N}{d}\) 種狀態，必須滿足： \(2^T \ge \binom{N}{d} \implies T \ge \log_2 \binom{N}{d} \approx d \log_2 \frac{N}{d} + O(d)\)
2. 機率模型下的香農熵下界（Shannon Entropy Bound）： 若每個個體獨立以機率 \(p\) 呈陽性，則母體狀態向量 \(\mathbf{X} \in \{0, 1\}^N\) 的聯合香農熵為 \(H(\mathbf{X}) = N H_2(p)\)。由於每次檢測最多提取 \(1\) 位元資訊，任何無差錯群測試演算法的期望檢測次數必滿足： \(\frac{\mathbb{E}[T]}{N} \ge H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)\)

以 \(N = 1,000, d = 1\)（\(p = 0.001\)）為例：單獨檢測需 \(1,000\) 次，多夫曼二階段法需 \(63\) 次，而資訊理論下界僅為 \(\lceil \log_2 1000 \rceil = \mathbf{10}\) 次！

3. 自適應群測試 vs. 非自適應群測試兩大範式

3.1 自適應群測試：黃氏廣義二分搜尋與「12枚假幣問題」

在自適應群測試（Adaptive Group Testing）中，每一次檢測都可以根據前一次檢測的結果動態調整檢體池：

• 當 \(d = 1\) 時，經典的二分搜尋（Binary Splitting）每次將候選集對半切分，每次檢測陽性與陰性機率均為 \(1/2\)（滿載 \(1\) 位元資訊），僅需 \(\lceil \log_2 N \rceil\) 次（\(1,000\) 人僅需 \(10\) 次）即可鎖定陽性者。
• 當 \(d > 1\) 時，黃光明（Frank K. Hwang, 1972）的廣義二分搜尋演算法（Generalized Binary Splitting）每次從剩餘 \(n\) 個檢體中切出大小為 \(2^\alpha \approx n/d\) 的子池進行測試（使得該池呈陰性的機率接近 \(1/2\)）。若呈陰性則一次排除 \(2^\alpha\) 人；若呈陽性則在該子池內進行 \(\alpha\) 次二分搜尋找出 \(1\) 名陽性者。總檢測次數達到 \(T = d \log_2(N/d) + O(d)\)，完美逼近資訊理論下界！

這一「最大化單次測試資訊熵」的思想在1945年著名的「12枚假幣天平問題」中得到了最精彩的展現：12枚硬幣中有1枚假幣（不知偏重還是偏輕，共 \(12 \times 2 = 24\) 種可能狀態）。天平每次稱重具有左傾（\(-1\)）、平衡（\(0\)）、右傾（\(+1\)）三種輸出（三元測試，每次最多提供 \(\log_2 3 \approx 1.585\) 位元資訊），因此 \(3\) 次稱重最多可區分 \(3^3 = 27 \ge 24\) 種狀態。若第一次在左右盤各放6枚，天平必然傾斜（不可能平衡），三元測試退化為二元測試（剩12種狀態 \(> 3^2 = 9\)），導致無解；唯有第一次在左盤放4枚、右盤放4枚、盤外留4枚，將24種狀態均勻分割為 \(8 : 8 : 8\) 三支，並在第二次稱重時將「疑似偏重」與「疑似偏輕」的硬幣在左右盤之間交叉輪換，才能在3次內100%鎖定假幣及其輕重！

自適應方法的致命工程瓶頸：在 RT-PCR 核酸檢測或基因定序中，每一輪 PCR 擴增需要 \(2 \sim 3\) 小時。若對 \(1,000\) 個檢體執行 \(10\) 輪自適應二分搜尋，必須串列等待 \(10 \times 3 = 30\) 小時，且反覆開蓋移液極易造成交叉污染。因此，實際高通量篩檢迫切需要將所有測試在同一輪（單階段）平行完成！

4. 非自適應組合群測試（NAGT）與析取矩陣（Disjunct Matrix）

4.1 布林測試矩陣 \(\mathbf{M}\) 與邏輯或（OR）疊加模型

1964年，考茨與辛格爾頓（Kautz & Singleton）創立了非自適應群測試（NAGT）與疊加碼（Superimposed Codes）的代數理論。我們將 \(T\) 次平行混檢與 \(N\) 個檢體的關係表示為一個 \(T \times N\) 的二元測試矩陣 \(\mathbf{M} \in \{0, 1\}^{T \times N}\)，其中 \(M_{i, j} = 1\) 表示檢體 \(j\) 被加入第 \(i\) 個混合池。

設未知的個體狀態向量為 \(\mathbf{x} \in \{0, 1\}^N\)（陽性集合 \(S = \{j \mid x_j = 1\}, |S| \le d\)），則觀測到的 \(T\) 維檢測結果向量 \(\mathbf{y} \in \{0, 1\}^T\) 是矩陣 \(\mathbf{M}\) 中對應於陽性集合 \(S\) 的各行向量（column vectors）的按位元布林邏輯或（Boolean OR）疊加：

4.2 \(d\)-可分矩陣 vs. \(d\)-析取矩陣（\(d\)-Disjunct Matrix）與 COMP 解碼

• \(d\)-可分矩陣（\(d\)-Separable Matrix）：任意兩個不同的大小不超過 \(d\) 的行子集 \(S_1 \neq S_2\) 的邏輯或疊加結果均不相同。雖然資訊理論上可唯一還原 \(S\)，但解碼需要遍歷 \(\binom{N}{d}\) 種組合，計算複雜度高達 \(O(N^d)\)。
• \(d\)-析取矩陣（\(d\)-Disjunct Matrix）：任意一個行 \(j_0 \notin S\) 的非零位置集合（支撐集 \(\text{supp}(\mathbf{M}_{*, j_0})\)），絕不完全包含於任意其他 \(d\) 個行的支撐集之聯集： \(\text{supp}(\mathbf{M}_{*, j_0}) \not\subseteq \bigcup_{j \in S} \text{supp}(\mathbf{M}_{*, j}) \qquad (\forall |S| \le d, \; \forall j_0 \notin S)\) 這意味著：對於每一個陰性個體 \(j_0 \notin S\)，必定至少存在一個「見證測試列 \(i^*\)」，使得 \(j_0\) 參與了測試 \(i^*\)（\(M_{i^*, j_0} = 1\)），而所有 \(d\) 名陽性個體均未參與測試 \(i^*\)（從而測試 \(i^*\) 的結果必為陰性 \(y_{i^*} = 0\)）！

  flowchart TD
    subgraph DisjunctTW["d-析取矩陣（d-Disjunct Matrix）的幾何保證"]
        ColS["d 個陽性行的布林或疊加向量<br/>y = ⋁_{j ∈ S} M_{*, j}"]
        ColJ["任意陰性檢體 j0 ∉ S 的行向量<br/>M_{*, j0}"]
        Witness["必然存在見證測試列 i*：<br/>M_{i*, j0} = 1 且 y_{i*} = 0（該池檢測呈陰性！）"]
        ColS --> Witness
        ColJ --> Witness
        Witness --> Result["陰性個體 j0 絕不會被陽性行掩蓋：<br/>線性時間 COMP 解碼實現零偽陽性與零偽陰性！"]
    end

憑藉 \(d\)-析取性質，我們可以使用極簡的 COMP（組合正交匹配追蹤）演算法在 \(O(TN)\) 線性時間內完成解碼：凡是參與過任何一次陰性測試（\(y_i = 0\)）的檢體全部排除為陰性，剩餘未被排除的檢體即100%為全部真陽性個體！ 組合學定理（D’yachkov-Rykov / Ruszinkó / Füredi）證明了零誤差 \(d\)-析取矩陣的列數下界為 \(T = \Omega\left(\frac{d^2}{\log d} \log N\right)\)，而機率構造與顯式構造均可達到 \(T = O(d^2 \log N)\)。

4.3 二維網格混檢的「幽靈陽性」與有限體里德-所羅門多項式設計

在實驗室中，若將 \(N = 100\) 個檢體排成 \(10 \times 10\) 網格，按 \(10\) 橫列與 \(10\) 直行分別混合得到 \(T = 20\) 個測試池：當只有 \(d = 1\) 名陽性（如座標 \((3, 7)\)）時，第3列與第7行呈陽性，交點唯一確定陽性者（\(1\)-析取矩陣）。但若有 \(d = 2\) 名陽性位於 \((2, 4)\) 和 \((6, 9)\)，則橫列 \(R_2, R_6\) 與直行 \(C_4, C_9\) 均呈陽性，除了真陽性外，對角交點 \((2, 9)\) 和 \((6, 4)\) 也會出現「橫列與直行皆為陽性」的假象（幽靈陽性 / 影子陽性）！

為了徹底消除幽靈陽性，Kautz 與 Singleton 提出了有限體 \(\mathbb{F}_q\) 上的里德-所羅門（Reed-Solomon）多項式混檢設計：將每個檢體 \(j\) 映射為有限體 \(\mathbb{F}_q\) 上次數不超過 \(k-1\) 的多項式 \(P_j(x) \in \mathbb{F}_q[x]\)（共可容納 \(N = q^k\) 個檢體），並在 \(w\) 個不同方向（求值點 \(x_1, \dots, x_w \in \mathbb{F}_q\)）上按照 \(y = P_j(x_m) \pmod q\) 進行分組混檢。因為兩個不同 \((k-1)\) 次多項式至多在 \(k-1\) 個點相交，只要選取方向數滿足 \(w \ge d(k-1) + 1\)（例如 \(q=11, k=2\) 時僅取橫列、直行、斜對角線 \(w=3\) 個方向共 \(T = 33\) 個測試池），就能在單輪測試中無歧義地分離任意 \(d=2\) 名陽性者！

5. 雜訊群測試、壓縮感知與現代工程應用

1. 稀釋效應與抗噪群測試（Noisy Group Testing）：針對混合過多檢體導致病毒濃度稀釋（PCR 的 \(\text{Ct}\) 值上升 \(\log_2 k\)）及偽陰性/偽陽性雜訊，透過構造具有 \(2e+1\) 個見證列的容錯析取矩陣並結合 NCOMP 演算法、置信傳播（Belief Propagation）或線性規劃解碼（LP Decoding），可自動糾正多達 \(e\) 次檢測錯誤。
2. 與壓縮感知（Compressed Sensing）的對偶性：坎德斯（Candès）、陶哲軒（Tao）與多諾霍（Donoho）建立的壓縮感知理論，本質上是將群測試從布林邏輯或（OR）推廣到了實數體上的稀疏線性測量 \(\mathbf{y} = \mathbf{\Phi}\mathbf{x}\)。當利用 PCR 螢光定量 \(\text{Ct}\) 值進行定量群測試（Quantitative Group Testing）時，測試次數可突破 \(d^2 \log N\) 瓶頸，進一步壓縮至 \(O(d \log(N/d))\)。
3. 多址通道碰撞消解與 COVID-19 P-BEST 篩檢：從無線通訊中的樹形碰撞分解協定（Capetanakis, 1979）、高速路由器識別巨量流量的 Count-Min Sketch，到 2020 年以色列團隊發表於 Science Advances 的 P-BEST 新冠核酸混檢方案（利用 \(48 \times 384\) 的 Kautz-Singleton 矩陣，僅用 \(48\) 個測試池在單輪 PCR 中同時篩檢 \(384\) 人，通量提升 \(8\) 倍），群測試與組合搜尋的數學智慧正在現代資訊與生命科學中持續閃耀。