抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

未婚夫问题

假如现在有n个求婚者,被分别标记为1,2,3…N,她们将按顺序被你面试,你每次都必须选择接受或不接受,一旦你接受了其中一个,那么就无法面试后面的人.因此你必须在无法面试后面的人的情况下选出当下最优者.

由于无法预知这些求婚者的平均情况,所以我们必须先面试前k个人,从第k+1个人开始,一旦发现更优者就立即选择她.

关键变量

这个问题中有三个主要的关键变量

最优点x

顾名思义,最优点就是最佳求婚者出现的位置,我们的最终目标是找到最优点,如果不能,那就尽可能让找到最优点的概率最大

停止点k

在停止点 k 之前的所有求婚者都将被拒绝,而她们之间的最优者将被作为面试之后的求婚者的标准,如果发现比她们之间的最优者更优的人,就立即接受她

次优点λ

在最优点 x 之前的最佳求婚者出现的位置就是次优点.我们希望次优点 λ 出现在停止点 k 之前,而最优点 x 出现在 k 之后

概率模型

当最优点 x 出现在停止点 k 之前时,计算没有意义,因为最优点已经被排除了

当最优点 x 出现在停止点 k 之后时,总共有(n-k)个情况,由于 x 出现的位置是随机的,总共有 n 个位置,所以所有情况发生的概率都是1n\frac 1n

只有次优点 λ 出现在前 k 个位置时,我们才能准确地找到最优点 x ,而次优点出现在前k个位置的概率为kx1\frac{k}{x-1}

因此我们可以计算出找到最佳求婚者的概率

P=x=k+1n1nkx1=knx=kn11xP=\sum\limits_{x=k+1}^{n}\frac 1n \cdot \frac k{x-1}=\frac kn \sum\limits_{x=k}^{n-1}\frac 1x

我们可以使用定积分得到PP的上下界

kndxxx=kn11xk1n1dxx\int_k^n\frac{dx}{x} \leq \sum\limits_{x=k}^{n-1}\frac 1x \leq \int_{k-1}^{n-1}\frac {dx}x

这两个定积分非常简单,因此这里直接给出结果

knlnnkPknlnn1k1\frac kn \cdot \ln \frac nk \leq P \leq \frac kn \cdot \ln \frac{n-1}{k-1}

如果希望PP尽可能大,则需要PP的下界尽可能大,于是我们对kk求导并令导数为0

dPdk=lnnk1n=0\frac{dP}{dk}=\frac{\ln \frac nk-1}{n}=0

解方程,得k=nek=\frac ne

显然当k=nek=\frac ne时,PP取到最大值36.8%36.8\%

因此对于任意的n,只需要将前36.8%36.8\%的数据作为参考,就能以最大概率在之后选出最优解

随机排列

如果想要验证上面的问题,就需要用到随机排列的数组.

均匀随机排列

均匀随机排列是指产生1~n的每一种排列的概率完全相同,即产生某一种排列的概率为全排列的倒数

给定序列[1,2,3, … ,n],通过将这些数字随机地变换以使数组随机化,从而达到均匀随机排列.优先级数组就是一种得到均匀随机排列得方法

优先级数组

对数组A,给定另一个数组P,在P中随机地生成一个大范围整数,并根据P[i]的大小来调整A[i]的位置.例如A=[1,2,3,4,5],而P=[13,62,6,19,52],那么调整后的序列就是[2,5,4,1,3]

但是这种方法有一个缺陷,即必须确保数组P的每一项都唯一,幸运的是,你只需要扩大随机数范围就可以尽可能保证不出现重复

该方法代码较为简单,故不做演示

EiE_i表示第 i 个元素被分配到第 i 个位置,则每个元素都被分配到自己对应的位置的概率为

P=i=1nP(Ei)P=\bigcap\limits_{i=1}^nP(E_i)

显然当i=1i = 1时,E1=1nE_1=\frac 1n,因为总共有n个元素.当 i ≥ 2 时,

P(Ei)=P(Eik=1i1Ek)P(E_i)=P\left(E_i|\bigcap\limits_{k=1}^{i-1}E_k\right)

所以,在前 i-1 个元素的位置都已经确定的情况下,P(Ei)=1ni+1P(E_i)=\frac{1}{n-i+1},于是我们得到

P=i=1nP(Ei)=i=1n1i=1n!P=\bigcap\limits_{i=1}^{n}P(E_i)=\prod\limits_{i=1}^{n}\frac 1i=\frac 1{n!}

所以,使用优先级数组方法获得等同排列的概率恰好为全排列的倒数

实际上,对于数组A的任意一个随机排列S,只需要修改一下E的定义,我们都可以使用上述方法证明出 A[i] 恰好被分配到 S 数组中的指定位置 j 的概率为1n!\frac 1{n!}

评论