假设在 $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$ 的各列向量的按位布尔逻辑或（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 DisjunctCN["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$ 倍），群测试与组合搜索的数学智慧正在现代信息与生命科学中持续闪耀。