作者：胡旭东，中国科学院数学与系统科学研究院研究员
作者简介：胡旭东，中国科学院数学与系统科学研究院，研究员，博士生导师，中国运筹学会理事长。1985年毕业于清华大学，获应用数学专业学士学位，1989年毕业于中国科学院应用数学研究所，获运筹与控制论专业博士学位。自1989年始，一直在中国科学院从事运筹学的理论研究和教学工作，主要研究方向为组合优化、网络博弈、近似算法。2012年被评为第五届“全国优秀科技工作者”，2016年获“中国科学院朱李月华优秀教师奖”。
近日，全国上下都还处在抗击疫情的阶段。这两个多月以来，大家持续在关注新冠肺炎确诊病例数，也知道确诊病例时需要进行核酸检测，而且每一次检测既需要花费时间也需要花很多钱。
下面我就给大家介绍一下与血液检测相关的数学模型和理论：如何应用数学的方法，用最少的成本（检验次数和时间），在大量的血液样本中准确地检验哪些是阴性的（好的），哪些是阳性的（坏的）。
在第二次世界大战期间，美国政府因战事需要征集了大量的年轻人参军。在征兵过程中需要体检，其中一个环节就是验血，用来筛查出应征参军的报名者中携带淋病病毒的年青人。通常的筛查方法是采集血样以后，对它们一个一个地进行检测，我们不妨称为「逐一检测法」。1943年 R. Dorfman 为美国公共健康服务和筛选服务系统设计了一个「组合检测法」[1]：
这样检测一个样本组可能出现的结果：
不难看出，如果在所有样本中阳性的比较少，那么组合检测法会减少大量的检测次数；而这正是当年征兵进行血液检测时的情形（现在每年高考学生进行体检时也类似）。可是如果在所有样本中阳性的比较多，那么组合检测法很有可能不仅不会减少检测的次数，还会增加检测的次数。
由此就自然地产生了一个数学问题：什么时候组合检测法可以减少检测的次数，什么时候不可以呢？1960年P. Ungar 对这个问题进行了研究[2]。他假设所需检测的个样本有个是阳性的，其中；每组可以包含任意多的血液样本（不再限定最多5个样本），而且每一个样本可以重复使用（一个血液样本可以分装在很多瓶子里）。在这些假设下，他证明了如下定理（大意是：当少于 的样本是阳性的时候，组合检测法平均需要的检测次数比逐一检测法需要的检测次数少）：
R. Dorfman 和P. Ungar 等人对血液检测问题的研究激发了很多后续的相关研究，很多有意思的数学模型和方法也先后被提出来，并逐渐形成了一个研究方向：组合检测/搜索。下一节我将给大家介绍这个方向中一个非常有趣的数学猜想。
上一节讲到，1943年 R. Dorfman提出了一个组合检测法[1]：将若干个样本放在一起进行检测。如果检测结果显示是阴性的，那么这个组里的所有样本都是阴性的；如果检测结果显示是阳性的，那么再将这个组里的样本逐一检测。1960年P. Ungar 对这个问题进行了研究[2]。他考虑的是一种「概率模型」：假设所需检测的个样本有个是阳性的，其中每一个样本可以有很多备份，每组可以包含任意多的血液样本（备份）。在这些假设下，他证明：当时，组合检测法平均需要的检测次数比逐一检测法需要的检测次数少。
应用实践和理论分析都表明，当大量的待检测样本中坏的样本不是很多时，比如，高考考生体检验血，或者新兵入伍复查体检验血，组合检测法比逐一检测法需要的检测次数要少。
今天我来介绍「组合模型」：假设事先已经知道所给的个样本中有个是阳性的，其中。（未经检测就知道有个是阳性的，这个假设不合理，是吧？我将在下一次介绍当这个假设不满足时，如何设计组合检测法。）下面先考虑最简单的情形，看看组合检测法好呢？还是逐一检测法好呢？
当时（只有1个样本是坏的），可以二分技巧快速检测到这个坏的样本，亦即将个样本尽量平均分成两组A和B，先检测A组；
上面的图示给出了用组合检测法对个样本的检测过程，检测开始前已知只有1个是坏样本，但是不知道哪一个样本是坏的。可以看出：当样本3是坏样本时，用2次检测就可以找到它；但是其他情况都需要3次检测。经过简单的计算可知：基于二分技巧的组合检测法用次检测一定可以找到那个坏的样本。
另外，当时（只有1个样本是好的），此时使用组合检测法是没有任何意义的，因为将任意两个样本放到一起进行检测，（不用检测就可以推断出）结果一定是阳性的，所以逐一检测法是最好的。
上面是两个最极端的情形：只有一个样本是坏的，或者只有一个样本是好的。前一种情形，组合检测法最好，后一种情形，逐一检测法最好。下面我们来考虑非极端的情形。比如，，，采用组合检测法7次检测就可以了（建议你自己试一试），比逐一检测法用的检测次数少一次。而当，，你会发现采用组合检测法需要8次检测才可以，与逐一检测法用的检测次数是一样多。
经过上面的初步分析，我们自然就会提出如下的数学问题：
❝什么时候组合检测法比逐一检测法用的检测次数少？亦即，给定个样本，并且已知其中有个样本是坏的，当不超过多少时组合检测法用的次数少于?
❞
1971年F. K. Hwang（黄光明）研究了上述问题[3]。他将上述问题称为「Group Testing Problem」，并用 表示最优检测法所需次数。显然，当不等式取等号时，就表示逐一检测法是最优的。他证明：当时，，亦即，若已知有以上的样本是坏的，则逐一检测法是最好的。
1981年F. K. Hwang等通过进一步的研究[4]，证明：当时，，亦即，若已如有以上的样本是坏的，则逐一检测法就是最好的。同时，他们提出了如下猜想：
❝Hu-Hwang-Wang 猜想:当时，。
❞
上述猜想成立意味着：若已知有以上的样本是坏的，则逐一检测法是最好的。
1982年D.-Z. Du（堵丁柱）与F. K. Hwang合作对上述猜想进行了研究[5]。他们证明：当时，，亦即，若已知有以上的样本是坏的，则逐一检测法就是最好的。尽管已经非常接近，这个结果也已发表近四十年了，但是至今还未出现更好的结果。「Hu-Hwang-Wang 猜想」已成为了组合检测/搜索研究方向的一个著名难题。大家有没有兴趣挑战一下？
下一节我将给大家介绍一下，当我们得到了个（血液）样本，但不知道关于它们的任何信息：既不知道好的样本多还是坏的样本多，更不知道究竟有多少个是坏的样本，我们又该如何设计组合检测方法呢？
[1] Robert Dorfman, The Detection of Defective Members of Large Populations, The Annals of Mathematical Statistics, 14 (4)(1943), 436-440.
[2] Peter Ungar, The Cutoff Point for Group Testing, Communications on Pure and Applied Mathematics, XIII (1960), 49-54.
[3] F. K. Hwang, A minimax procedure on group testing problems, Tamkang Journal Mathematics, 2 (1971), 39-44.
[4] M. C. Hu, F. K. Hwang and J. K. Wang, A boundary problem for group testing, SIAM Journal on Algorithms and Discrete Methods, 2 (2) (1981), 81-87.
[5] D.-Z. Du and F. K. Hwang, Minimizing a combinatorial function, SIAM Journal on Algorithms and Discrete Methods, 3 (1982), 523-528.
本文转自：柚子优化。感谢作者授权转载。
联系客服
