首页 > 代码库 > 选择爱人的数学方法(经典秘书问题)

选择爱人的数学方法(经典秘书问题)

Kepler(开普勒,1571年12月27日-1630年11月15日),德国天文学家、数学家,十七世纪科学革命的关键人物。

这样一位伟大的人物在1611年遇到一个问题,他的夫人患匈牙利斑疹伤寒(Hungarian spotted feve)过世,为了照顾孩子、打理家务,Kepler 需要重新寻找一位夫人。身为严谨的科学家,他认真记录下了“面试”11位夫人“候选人”的过程。

第一位,“口臭”,Kepler写到。

1400550466.jpg

第二位,“养尊处优”。

1400550536.jpg

第三位:“已经许配给一个有私生子的人,太复杂了”。

1400550575.jpg

第四位:“身材高挑,气质不凡”。

1400550618.jpg

不过,Kepler 想看看第五个,因为有人告诉他,第五位女孩儿集“谦虚、节俭、勤奋...”等优点于一身。于是,Kepler 犹豫了,而且犹豫了很长时间,以至于第四位和第五位女孩儿都不耐烦地离开了。

第六位是一个“衣着华丽的大小姐”,这把Kepler吓了一跳,他有点担心高昂的婚礼费用。

1400550660.jpg

第七位女孩儿很迷人,Kepler 也很喜欢她。由于没看完这11位“候选人”,Kepler 心有不甘。他让这位女孩儿等他看完“候选人”再做决定。不愿意等人的第七位女孩儿也离开了。

1400550747.jpg

第八位女孩儿,Kepler 没怎么关心。

1400550784.jpg

第九位女孩儿“体弱多病”;第十位女孩儿有着“对于没什么要求的普通人”也没办法接受的体型;最后一位女孩儿,还是个小姑娘,也不适合。

11位“候选人”都看完了,一个也没有约成。Kepler 开始想,哪里出错了?

1400550842.jpg

Kepler 所需要的,是优化策略,一种不能保证成功但能将失望降至最低的方法。数学家们觉得,我们能算出这样的公式来。                                     本文地址

如果你有自己的候选列表,爱人也好,约会也好,工作也好,这方法都管用。规则很简单:只要你的选择有限,你可以做一个列表,然后挨个来。再一次声明,不总能成功。但对数学家来说,足够了。

这个问题甚至有个名字:(开普勒的)婚姻问题。后来,又被衍生为经典秘书问题(Classic Secretary Problem)。比如,你有20个候选人要逐一面试,在面试之后,你必须决定要不要。要,选择结束;不要,那就喊下一位。不能回头。一旦决定聘用,问题结束。

根据马丁·加德纳在1960年的说法,最好的办法是,先面试前36.8%的候选人,但不录用他们。在此之后,一旦遇到比前面这36.8%里最好的还好的,立马录用。

为什么是36.8%呢?这个答案牵扯到e,1/e=0.368(关于这个概率的证明可以参考 维基百科)。很显然,这个公式经过了无数次的验证。尽管它不能保证结果最优,但你有36.8%的机会。对于11个“候选人”来说已经足够了。

如果,当时Kepler 用了这个公式,会怎样呢?11的36.8%的是4,所以他要pass掉前四位候选人,从第五位开始,只要比前四位好,Kepler 就应该求婚。也就是,经过一番折腾后,Kepler 会和第五位女孩儿结婚。(你还见记得第五位是谁吗?)

如果Kepler 当时知道这个公式(这也是当今数学上最优停止的一个例子),他便能省去后后面一批人的约会了。

 

 

另外还可以参考: 秘?书?问?题?最?优?解  ;善科网  ;经典问题“秘书问题” 深入研究

 

【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3747946.html