很好玩的一个算法 微软钻石题

引言

前段时间在ADSP课上，作为课间小插曲，老师提出了一个微软的钻石面试题，题目的描述是如下：

一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗？

课堂上有人给出了一种策略：前五层的钻石都不拿，而只是记录下最大的那一颗，在后面的五层里，只要遇见比所记录大的就拿。若没有大的，就拿最后一颗。还有人根据钻石的大小事服从正态分布进而进行参数估计，从而得出预期的最大的层数。其本质是根据已有的资料预计后面的大小从而做出选择。适逢上周有空，看到关于男生追求女生的一个数学模型《炮灰模型——女生选择追求者模型》，细想后发现此问题与微软这道面试题挺像的，可以将其模型和结论扩展到此问题上，并且结果也挺有意义的。首先从“炮灰模型”说起。

网上广泛转载的《炮灰模型——女生选择追求者模型》据说是Tsinghua University的一个学生Geng Quan写的，后有网友的润色和加工和开拓。其所提问题个人觉得与数学家Merrill M. Flood 在1949年“未婚妻问题”类似。而这个问题的精妙之处在于，在微积分界叱咤风云的自然底数e，竟也出人意料地出现在了这个看似与它毫不相关的问题中。还是从我们熟悉的某类节目说起。

背景介绍

在每期由两个光头主持的很火爆的某节目上，面对一位位男嘉宾，24 位单身女生要做出不止一次“艰难的决定”：到底要不要继续亮灯？把灯灭掉意味着放弃了这一次机会，继续亮灯则有可能结束节目之旅，放弃了未来更多的选择。

每一个女生都渴望找到自己心中的白马王子，找到自己一生的幸福。但是面对追求者们，女生应该是选择还是拒绝，怎样才能以最大的可能找到自己的Mr. Right呢？如果遇到了一个优秀的男生，应该接受还是拒绝呢？如果接受了他，万一下一个更好的话那可就亏大了；可如果为此而拒绝掉一个又一个好男人，也会面对着“过了这个村就没这个店”的风险。说不定白马王子们都已经擦肩而过，到最后就只剩下。。。，当初的拒绝明显得不偿失。

由于没人能知道真正的缘分何时到来，没人能知道下一个来表白的男生会是什么样子，接受表白的时机早晚实在很难决定。而运用数学中概率论的知识对女生选择追求者的这一过程进行数学建模，得到女生的选择的最优策略以作参考。

模型假设（Geng 和 Flood）

假设一个女生愿意在一段时间中和一位男生开始一段感情，并且在这段时间中有N个男生追求这位女生。说明：这里的N不是事先确定的，每个女生根据自身条件，并结合以往的经历和经验，猜测确定这个数字N。比如其它各方面都相同的两个女生，一般来说，PP气质佳的女生就要比不PP的女生N值相对要大一些。在适合这个女生的意义上，假设追求者有好有坏，任何两个男生都是可以比较的，而且没有相等的情况。这样我们对这N个男生从1到N进行编号，其中数字越大表示越适合这个女生。这样在这段时间中，女生的Mr. Right就是男生N了。现在问题变成面对这N个追求者应该以怎样的策略才能使得在第一次选择接受的男生就是N的可能性最大，注意到这N个男生是以不同的先后顺序来追求这位女生的。

为了将实际复杂的问题进行简化，我们做出下面几条合理的假设：
1、 N个男生以不同的随机顺序向女生依次表白，即在任一时刻不存在两个或两个以上 的男生向这位女生表白的情况的发生，而且任何一种顺序都是完全等概率的。
2、 面对表白后的男生，女生只能做两种：接受和拒绝，不存在暧昧或者其它选择。
3、 任一时刻，女生最多只能和一位男生谈恋爱，不存在脚踏多船的情况。
4、 已经被拒绝的男生不会再次追求这位女生。

基于上述假设，我们想要找到这样一种策略，使得女生以最大的概率在第一次选择接受的那个男生就是N=Mr. Right。

模型建立

先考虑最简单的一种策略，如果一旦有男生向女生表白，女生就选择接受。这种策略下显然女生以1/N的概率找到自己的Mr. Right。当N比较大的时候，这个概率就很小了，显然这种策略不是最优的。

基于上面这些假设和模型，聪明的 MM 会想到一个好办法：先和前面几个男生玩玩，试试水深；大致摸清了男生们的底细后，再开始认真考虑，对于最先表白的M个人，无论女生感觉如何都选择拒绝；以后遇到男生向女生表白的情况，只要这个男生的编号比前面M个男生的编号都大，即这个男生比前面M个男生更适合女生，那么女生选择接受，否则选择拒绝。从数学模型上说，就是先拒掉前面M个人，不管这些人有多好；然后从第M+1个人开始，一旦看到比之前所有人都要好的人，就毫不犹豫地选择他。不难看出，k 的取值很讲究，太小了达不到试的效果，太大了又会导致真正可选的余地不多了。这就变成了一个纯数学问题：在男生总数N已知的情况下，当M等于何值时，按上述策略选中最佳男生的概率最大？

下面以N=3为例说明：

三个男生追求女生，共有六种排列方式：

1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1

如果女生采用上述最简单的策略，那么只有最后两种排列方式选择到Mr. Right，概率为2/3!=1/3。

如果女生采用上面我们提出的策略，这里我们取M=1，即无论第一个人是否优秀，女生都选择拒绝。然后对于之后的追求者，只要他比第一个男生更适合女生就选择接受，否则拒绝。 基于这种策略，“1 3 2”、“2 1 3”、“ 2 3 1”这三种排列顺序下女生都会在第一次做出接受的选择时遇到“3”，这样我们就把这种概率增大到3/3!=1/2。

现在我们的问题就归结为，对于一般的N，什么样的M才会使这种概率达到最大值呢？（在这种模型中，前面M个男生就被称为“炮灰”，无论他们有多么优秀都要被拒绝）

根据上面的模型假设，我们先找到对于给定的M和N(1，女生选择到Mr. Right的概率的表达式。

把1到N个数字进行排列共有N!种可能。对于某个固定的M，如果最适合的人出现在了第P个位置（M< P≤N），要想让他有幸正好被MM选中，就必须得满足前P-1个人中的最好的人在前M个人里，这有M/(P-1) 的可能。即可归纳为下面的亮点：

当数字N出现在第P位置（M≤N），如果使上述策略在第一次选择接受时遇到的是N，排列需要满足下面两个条件：

1、N在第P位置
2、从M+1到P-1位置的数字要比前M位置的最大数字要小

考虑所有可能的P，我们便得到了试探前M个男生之后能选中最佳男生的总概率P(M)：

模型求解

这个问题可以方便的通过计算机进行数值求解。
用 x 来表示 M/N 的值，并且假设N充分大，则上述公式可以写成：

对 -x · ln x 求导，并令这个导数为 0，可以解出 x 的最优值，它就是欧拉研究的神秘常数的倒数—— 1/e ！即此时
M=N/e。

结果分析：由上述分析可以得到如下结论：为了使一个女生以最大的概率在第一次选择接受男生时遇到的正是Mr. Right，女生应该采用以下的策略：

拒绝前M=[N/e]或者[N/e]+1个追求者，当其后的追求者比前M个追求者更适合则接受，否则拒绝。

也就是说，如果你预计求爱者有 n 个人，你应该先拒绝掉前 n/e 个人，静候下一个比这些人都好的人。假设你一共会遇到大概 30 个，就应该拒绝掉前 30/e ≈ 30/2.718 ≈ 11 个求爱者，然后从第 12 个求爱者开始，一旦发现比前面 11 个求爱者都好的人，就果断接受他。由于 1/e 大约等于 37%，因此这条爱情大法也叫做 37% 法则。
不过，37% 法则有一个小问题：如果最佳人选本来就在这 37% 的人里面，错过这 37% 的人之后，她就再也碰不上更好的了。但在游戏过程中，她并不知道最佳人选已经被拒，因此她会一直痴痴地等待。也就是说，MM将会有 37% 的概率“失败退场”，或者以被迫选择最后一名求爱者的结局而告终。

37% 法则“实测”！

37% 法则的效果究竟如何呢？我们在计算机上编写程序模拟了当 n = 30 时利用 37% 法则进行选择的过程（如果 MM 始终未接受求爱者，则自动选择最后一名求爱者）。编号越小的男生越次，编号为 30 的男生则表示最佳选择。程序运行 10000 次之后，竟然有大约 4000 次选中最佳男生，可见 37% 法则确实有效啊。

计算机模拟 10000 次后得到的结果

不知道了解此问题的女生，会不会多了一种分手的理由：不好意思，你是那 37% 的人⋯⋯对于男生，该模型残酷的，指出了炮灰存在的现实意义，正如伟大哲学家萨特所说“存在即是合理”，炮灰的不可避免性也许是对已经和即将成为炮灰的男生的宽慰。But,However，What’s more(^__^) ……，该模型的量化指标都是采自女生主观臆断，各个指标的合理性希望广大MM慎思之。

微软钻石问题

是时候回到原问题——“微软钻石题”上了。我们可以把每个钻石看做是前来表白的男生，MM坐电梯上楼对其进行选择，这样该问题就可以化为MM选择最佳追求者的问题了。即有10个追求者，要求MM拒掉的男生的人数M为多少时，才可以以最大概率找到Mr. Right？

因此将N=10代入（1）式，由于是离散化的且N不是很大，我们可以用遍历搜素进行求值，当然本问题用手工计算或计算器计算下就好了。经过计算可知M=3。

那么对于较大的N，我们给出MATLAB的结果：

仿真后可得随着N的增长，按此方案选择最优值在1/e附近。

结论：因此对于微软钻石选择问题的策略是：前3层都不拿钻石，并记录下最大的钻石的大小，然后从第四层开始，只要遇到比前三层都大的钻石就拿。

结论推广与讨论

1、众所周知生活中涉及到感情的事情是很复杂的，而且也是很微妙的，把所有可能影响的因素都考虑到几乎是不可能的。不过也说明了数学的强大。

2、设女性最为灿烂的青春为18-28岁，在这段时间中将会遇到一生中几乎全部的追求者（之前之后的忽略不计），且追求者均匀分布，则女性从18+10/e=21.7即22岁左右开始接受追求对自己最有利，这告诉我们，想谈恋爱找大四或研一的（有木有默默中枪的O(∩∩)O）。推而广之，若只考虑时间段研究生2.5年的话，则T/e=0.9197。也就是说，对于研究生，男生表白的最佳时刻在第二个学期的期末。若不考虑进入实验室后狭小的圈子的研二阶段，那么T=1/e=0.367.莫非是这学期12月份？--!

3、在文章中只考虑了N个男生表白的先后顺序是完全随机的，并没有考虑相邻两次之间的时间隔。如果把时间因素也考虑进去的话，在一个相对较短的时间中，可以近似的假设为齐次泊松过程，这样不仅可以得出女生应该选择上面的第M个男生的结论，而且找到男生表白的最佳时间在t=T/e时刻。 例如如果取时间段为大学四年的话，则T/e=1.4715。也就是说，在大学四年里，男生表白的最佳时刻在第三个学期的期末或寒假。但是这个模型假设 还没有考虑：女生分辨N 能力是在增长的，并不是一开始就能无失误的迅速判断；在大学阶段 18至22如果把她能接触到的男生放进一个集合A，那么max{A}会不断减小的，等到她审阅到N/e的时候恐怕已经没的选了（也就是说原模型不可以在时间段上任意推广）。而且如果这个时间段较长的话，那么男生追求可近似假设为了一个非齐次泊松过程，或者分段齐次泊松过程。