魔方吧·中文魔方俱乐部

标题: 验血问题 [打印本页]

作者: 铯_猪哥恐鸣 时间: 2010-4-12 19:01:04 标题: 验血问题

相传二战期间美国流行某传染病，其感染率为p（远小于一），这时刚好有人发明了一种仪器，只要有该病毒的存在，无论多么稀就能检测出病毒来，即对于一堆人，可以将他们的血混一起输入仪器，只要有一人干扰，仪器就会检测出阳性，若都没感染则显示阴性。现在有N（远大于一）个人报名入伍，需要进行该传染病的检测。问，军方应使用什么样的策略，使得最终期望的验血次数最少？

作者: yanzi7816 时间: 2010-4-12 19:03:54

吓我一跳。我还以为是广告....

作者: superacid 时间: 2010-4-12 19:14:32

占楼思考中..

作者: speedz 时间: 2010-4-12 19:17:10

先总体测一次，然后分组，这样逐渐分细？

[ 本帖最后由 speedz 于 2010-4-12 19:19 编辑 ]

作者: 夜雨听风 时间: 2010-4-12 19:18:16

the same to 3L

作者: 铯_猪哥恐鸣 时间: 2010-4-12 19:21:02

开放性问题，我自己都没找到答案，就像某个找女朋友问题一样，无法判断是不是最优的

作者: phileas 时间: 2010-4-12 19:29:59

初步想法：计算N*p，把人均分成 [N*p]+1 或者 [N*p]+2 份（如果N*p的小数部分大于 0.5，则取[N*p]+2，否则取 [N*p]+1）。
然后测试一下，按照数学期望，有至少一份是检测出来完全健康的，然后把剩下的人并到一起，继续均分。

作者: dkjiaoyang 时间: 2010-4-12 19:32:51

设：除了每人一次的最慢方法外，每人的血样需要X次测试。将人分为K组。
视X为随机变量，则X的分布列是（K[sup]-1[/sup]，1+K[sup]-1[/sup]；q[sup]K[/sup]，1-q[sup]K[/sup]），其中q=1-p
每人平均化验次数E[sub]X[/sub]=上述分布列对应的矩阵的值=1-q[sup]k[/sup]+k[sup]-1[/sup]
则只需要E[sub]X[/sub]＜1，即比每人单独化验要节省次数
PS：目前还没有想出更优解法~~~

[ 本帖最后由 dkjiaoyang 于 2010-4-12 23:36 编辑 ]

作者: dkjiaoyang 时间: 2010-4-12 19:38:40 标题: 回复 4# 的帖子

个人认为没有总体测一次的必要，顶多开始测一半

作者: 铯_猪哥恐鸣 时间: 2010-4-12 19:39:35

回7楼，不确定噢，其实是有很小的概率所有人都感染的。
当然也有一定概率没人感染

[ 本帖最后由铯_猪哥恐鸣于 2010-4-12 19:42 编辑 ]

作者: ynjyht 时间: 2010-4-12 19:47:49

人均验一次或分为K组验。
N个人平均验血的次数：N(1-q^k+1/k)
取(1-q^k+1/k)最少。。。

作者: 铯_猪哥恐鸣 时间: 2010-4-12 20:06:20

回8楼，还有更优的想法吗？

作者: flwb 时间: 2010-4-12 20:55:28

优选法,黄金分割,0.618

作者: superacid 时间: 2010-4-12 21:11:15 标题: 回复 13# 的帖子

对这题不一定吧

作者: Paracel_007 时间: 2010-4-12 23:34:01

概率问题最让我头疼了…

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)