在总共325种可能情形中,Yes -集有171种可能情形,No-集有154种可能情形。回答者会(贪婪地)选择回答“Yes”。实际上,提问者的策略就是要选择这样一个问题,其产生的Yes-集和No-集各自含有的可能情形尽可能一样多。可以验证:若提问者第③个问题改为问:“Is
?”,则相应产生的Yes-集和No-集所含有的可能情形分别为163和162。因而,问“Is ?”比问“Is ?”要更好。 J. Spencer [2]利用魔鬼策略和权函数法,证明提问者只要问不超过26个问题就可以猜出
的值,且24个问题是不够的,但他留下了一个疑问,用25个问题可以吗?1987年A. Pelc [3]通过更加精细的研究,最终证明了25个问题是可以的,从而彻底解决了乌拉姆的猜数问题。 至此,大家不难看出,乌拉姆的猜数问题实际上可以视为容错模型下的组合检测问题的一个非常特殊的情形:样本个数是1,000,000,回答者事先选定一个值
为,也就是第个样本是惟一的坏样本;提问者的针对一组数提一个问题相当于对相应的样本组做一次检测,回答者的回答“是”或“否”表示相应的检测结果是“阳性”或“阴性”(样本组中“含有”或“不含有”坏样本);回答者说谎相当于检测错误。 最后小结一下我这四次讲的模型和结果:如何用尽可能少的组合检测,在大量的血液样本中准确地检测出所有的坏样本。我介绍的方法基本都属于序贯方法:每次检测哪些样本组,要依赖以前的检测及其结果。一个序贯方法如果需要做
次检测才能检测出所有的坏样本,而每次检测需要时间的话,整个检测过程就可能需要时间。如果想缩短时间,那么除了尽可能地减少检测次数,还有一个方法就是在时间内同时(并行地)检测若干(而不是一个)样本组。下一次我就给大家介绍这种非序贯方法。