梦幻情人的概率

2013年12月1日1,3240

《算法之道》7.6  梦幻情人的概率

我们的情人寻找算法LOVER-FINDER能够让我们每次见到更优秀的异性时立即见异思迁,大大过了一把”良禽择木而栖,好男(女)择女(男)而爱”的瘾。而且更为重要的是,这样一种奢华的恋爱算法居然成本低廉,仅仅是对数级的O(c*ln n)!

一切似乎完美得不能再完美。

但仔细一想,发现这个算法还是有问题。虽然对数级成本在数量级上较低,但这毕竟是多次谈恋爱。而谈多次恋爱的成本毕竟是不少人在精神上、时间上和经济上负担不起的。如果你恰恰又是一个清教徒,则谈多次恋爱还有可能违背你的信仰原则。因此,你决定只能谈一次恋爱!

虽然你是清教徒,或者没有精神和精力去谈多次恋爱,但找到最好的伴侣却是人人都向往的!因此,一个自然的问题是:如果只谈一次恋爱,是否仍能找到称心如意的恋人呢?

那就得看你有没有这个本事啦!不过,这里的本事指的不是忽悠异性的本事,而是算法设计与分析的本事!

显而易见,既然只能谈一次恋爱,但又必须找到最称心如意的梦幻情人,我们便不得不在查看多个候选人的情况下选择一个人作为恋人。为帮助你达到此目标,婚姻介绍所允许你对候选人进行面谈(是见面,或者说相亲,不是真正的谈恋爱)。每次面谈完你必须马上决定是否与该候选人确定恋爱关系。如果决定谈下去,婚姻介绍所即完成使命,将不再提供任何候选人。而如果你不喜欢当前的候选人,则可要求婚姻介绍所换一个人。当然,婚姻介绍所最多提供n个候选人。

面谈虽然不如真正谈恋爱那么伤感情和花费金钱,但也是花费时间和精力的。由于时间和精力有限,你希望将面谈的人数限制在一个较小的范围。因此,你决定先面试k个人,并通通予以拒绝,然后在后面面试中出现的第1个超出前面这k个人的人就是你的恋人。如果后面再无比前面k个人都好的人,则第n个人就是你的恋人,即最坏情况下,你需要面试所有n个候选人。因此,我们新的更加节省费用的情人寻找算法(OPT-LOVE-FINDER(n))如下:

  1. 选择一个k<n。
  2. 面试婚姻介绍所介绍的前k个候选人,并予以拒绝。
  3. 后面出现的第1个超出前面这k个候选人的人就是恋人。
  4. 如果后面不出现超出前面k个人的人,则第n个人就是你的恋人。

这里我们要问的问题就是,应该如何确定k的取值,以使得你的恋人是所有n个候选人里面最好的概率最大!并且计算出这个概率!

对于很多人来说,这个问题乍看之下似乎无从下手。

但仔细分析题意可以看出(也许不容易看出),解答这个问题的步骤应该是先假设我们已经找到了某个k,然后计算在该选定k的取值下,我们获得最佳候选人的概率是多少。然后再根据计算出的概率表达式求极大值即可算出这个k的取值。

现在假定我们已确定了 k 值的大小。很显然,在OPT-LOVE-FINDER 算法的策略下,我们找到梦幻情人(最佳情人)的唯一可能是最佳人选出现在后面的n – k个人当中。如果最佳候选人出现的位置是i,则其前面i – 1个人里面的最优秀的人必须出现在前k个人里面;否则,该最优候选人将成为你的恋人,而不是整个n个候选人里面最好的人!

设E(i) 为候选人i是所有n个人里面最佳候选人的事件,E(k, i) 代表前i个人里面的最佳候选人出现在前k个人里面的事件,E 代表你的恋人是整个n个人里面最佳候选人的事件。

根据上述分析,我们有:

Pr[E]=Pr[E(k+1)E(k,k)]+Pr[E(k+2)E(k,k+1)]+...+Pr[E(n)E(k,n1)]=i=k+1nPr{E(i)E(k,i1)}

这里,Pr[E(k + 1)E(k, k)]代表的是第k + 1号候选人是最佳人选,并且前k个人里面的局部最佳人选出现在前k个人里的事件发生的概率;Pr[E(k + 2)E(k, k + 1)]代表的是第k + 2号候选人是最佳人选,并且前k + 1个人里面的局部最佳人选出现在前k个人里的事件发生的概率;Pr[E(n)E(k, n – 1)] 代表的是第n号候选人是最佳人选,并且前n – 1个人里面的局部最佳人选出现在前k个人里的事件发生的概率。

由于任何一个候选人是全局最佳人选的概率均等(如果不是这样,我们可以通过随机化手段使得该条件满足),我们有:Pr{E(i)} = 1/n, 且 Pr{E(k, i)} = k/i。因此,

Pr{E}=i=k+1nPr{E(i)E(k,i1)}=i=k+1nPr{E(i)}Pr{E(k,i1)}=i=k+1n1nki1=kni=kn11i=kn(i=1n11ii=1k11i)kn(ln(n1)ln(k1))=kn(lnn1k1)knlnnk

这样,我们就获得在k值给定的情况下,获得最佳人选的概率约为 knlnnk 。对此表达式求取极大值,我们得到 Pr{E} 在 k=ne 的时候获得最大值,并且这个最大值为 1e 。

我们的算法描述如下:

  1. 对所有的候选人进行随机排列。
  2. 面试前n/e个候选人,并予以拒绝。
  3. 后面出现的第1个超出前面这n/e个候选人的人就是恋人。
  4. 如果后面不出现超出前面n/e个人的人,则第n个人就是你的恋人。

根据上面的分析,新的情人寻找算法寻找到梦幻情人的概率为1/e,即约36%。但该算法的恋爱成本为常数,即c。而面谈的成本为 neci ,只有第1个情人寻找算法的约1/3。


阿连在课上提到的算法如下:(和上面提到的概率分析有差异)