2008-01-12 13:34| 
10 Comments | 本文内容遵从 SETI@home可以在杂乱的射电数据中搜寻独特的讯号，你能在大街上的嘈杂声中清晰分辨出一个尖细的女声大叫“亚美蝶”。这些现象都表明，有时对集合里的所有元素进行整体考察可以很快找出我们所要找的个体。去年我们搞合唱比赛时，我又想到了一个绝佳的例子：你可以在合唱声中清楚地听到是否有人跑调。考虑这样一个问题，假如合唱团里有一个人唱歌始终走调，但我听不出来是谁走调，只能听出当前正在唱歌的人中是否有唱走调了的人。那么，我如何才能迅速地揪出那个唱走调的人？利用经典二分法，我们可以在log2(n)次合唱后找出唱走调了的人。每一次，我都把剩下的人平均分成两组，然后选其中一组来合唱：如果听不到走调的声音，这一组的人就全部过关；如果听到有人走调，那另一组里的人都可以被排除了。递归地对剩下的组进行同样的操作，log2(n)次操作后必定可以找出那个唱歌走调的人。
现在的问题变得有些麻烦了。假如我们知道合唱队里有一个人唱歌爱跑调，但他不是总会跑调。具体地说，他只有1/2的概率唱错，但其余1/2的时间里他却唱得很准。现在，传统的二分法不再适用了，因为没有走调声已经不能起到排除的作用了。你能想出多少种可行的算法来找出那个人？下面提出一些可行的方法，你认为哪种方法更好？你能求出这些算法所需要的检测次数的期望值各是多少吗？
1. 不断地随机生成一个大小为n/2的子集并对其进行检测，直到某次不能通过检测为止，然后递归地对其进行操作。
2. 所选的子集大小为n/2是最优的吗？把上面这种方法的n/2改成n/a，常数a的最优值是多少？
3. 检测次数的期望值还可以更小吗？我们想到，每次都重新生成一个新的集合其实并不科学，新集合本身是否包含老鼠屎也是得碰碰运气的。因此，对方法1的一个合理改进是：把集合平均划分为两个部分，交替对它们进行检测直到某次检测没通过为止，然后对该组递归操作下去。这种方法真的比前两种好吗？它所需要的期望次数是多少？
4. 尝试对方法3进行改进。如果把集合平均划分成3份并循环进行检测，效果会不会更好一些？
1. 选取的子集有1/2的概率覆盖了我们要找的那个人，子集里有他而他这次恰好又唱走调了则有1/4的概率。因此，不管规模有多大，平均需要4次才能把规模缩小一半。因此，检测次数的期望值为4*log2(n)。为了方便比较期望值的大小，后面的答案我们一律表示成一个常数乘以log2(n)的形式。
2. 类似地，平均需要2a次检测才能把规模缩小到原来的1/a，因此总共花费的检测次数为2a*log2(n)/log2(a)。对函数求导，可得当a为e时函数值达到最小。此时的检测次数期望值为2e*log2(n)/log2(e)≈3.7683 * log2(n)。
3. 这个就经典了。设方法3里把规模缩小一半所需要的检测的期望次数为m，下面我们来看m应该等于多少。把n个人平均分成两组，我们要找的老鼠屎有1/2的概率在第一组，有1/2的概率在第二组。因此，第一次就测出问题来有1/4的可能，第二次就测出问题也有1/4的可能。对于剩下的1/2种情况，局面变得又和最开始一样，只是平均需要的检测次数比原来多了2。根据期望值的定义，有m=(1/4)*1 + (1/4)*2 + (1/2)*(m+2)，解得m=3.5。总的检测次数就是3.5 * log2(n)，它比前面两种方法都要好。你可能不同意上面求m的方法。这没啥，如果你不断对m进行迭代，你会发现展开出来的式子就是最标准的期望值定义。
4. 类似地，有m=(1/6)*1 + (1/6)*2 + (1/6)*3 + (1/2)*(m+3)，解得m=5。于是，把规模缩小到原来的1/3平均需要5次检测，总的检测次数为5*log2(n)/log2(3)≈3.1546 * log2(n)。
题目来源：IBM Ponder This Dec07
原文还从熵的角度探寻了问题的最优算法，感兴趣的读者可以去看一看
10 条回复
您也随便说几句吧：
sofa~~~~~
^_^
板凳
精彩~~
晕``居然还能从熵的角度来分析，太NB了吧。。。
基本的问题，但是较复杂。
用循环检测的方法,把集合平均划分成3.03396份,总次数为3.15447*log2(n)最小
不错
北京的冬令营北大秦腾就讲了这个……
[...] 二分思想真的是无所不在，即使在中文系的专业课中我们也能见到这个词。在语言学概论中我们提到，一个音位可以由一组区别特征确定下来，这些区别特征总是以只具有“是/否”、“有/无”等两种对立属性的“二元偶分组”形式存在，因为这样可以最方便最快捷地确定出一个元素。这有点像猜数字一样，我想一个数字后让你来猜，我告诉你你的猜测是大了还是小了。只是在这里，回馈的信息不再是大小，而是“辅音/元音”、“口音/鼻音”、“浊音/清音”、“送气/不送气”等形式逐层细分。这让人联想到5张卡片猜年龄的老把戏，一系列火星的称球问题，基于比较的排序算法的复杂度下界，或者经典的20q在线游戏。 一个有趣的事实是，相当多的人都错误地理解了“二分”这个词，但他们在生活中却拥有很强的二分意识。我们语言学概论的老师（这里就不说是谁了）在讲解二分时举了一个甚为荒谬的例子：如果你要在房间里找一根针，那么你可以把房间划分为两半，如果这一半找不到的话说明针一定在房间另一半，此时再把那一半分成两部分，不断分分分分分最后总能找到针的位置。这是这位老师无数荒唐的例子中的冰山一角，因为这个“二分”与搜索别无二致。这个“二分”的判断环节并不是即刻返回的，而且最关键的是它并不具有规模减半的功能，或者说一旦返回“真”后我们并不会再接着二分下去。如果让我来举例子的话，同样是拿找东西打比方，在合唱队中找出跑调了的人是一个绝佳的例子，因为在合唱中我们能轻易分辨出一个不和谐的声音（虽然无法准确判断这个声音是从哪儿传来的），不断叫当前的人的其中一半来合唱便可渐渐判断出那个人的位置。但讽刺的是，这老师在举这个错误例子的同时，竟然在不自觉地用二分法来调整课件的字号。他发现这一页ppt的字号太小了，我们可能看不清，于是希望让字号尽可能的大但又不致于大到显示不下。他开始尝试40号，发现字已经超出屏幕了；然后把字体改成20号，又觉得还能再大一些；进而又改到28号（工具栏上的字号调整以4为步长），最后确定到了24号字。 [...]
楼主你好，这个讲的很精彩。但是3，4里面求期望的方法我一时还很难理解，你能讲解一下吗？有没有相关资料讲述的