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

未婚夫问题

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

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

关键变量

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

最优点x

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

停止点k

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

次优点λ

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

概率模型

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

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

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

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

DearXuan

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

DearXuan

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

DearXuan

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

DearXuan

解方程,得

DearXuan

显然当k=n/e时,P取到最大值36.8%

因此对于任意的n,只需要将前 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的每一项都唯一,幸运的是,你只需要扩大随机数范围就可以尽可能保证不出现重复

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

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

DearXuan

显然当 i = 1 时,E1为1/n,因为总共有n个元素。当 i ≥ 2 时,

DearXuan

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

DearXuan

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

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

评论