麦穗理论
有一天,柏拉图问老师苏个拉底什么是爱情?老师就让他先到麦田里去,摘一颗全麦田里最大最金黄的麦穗来。期间只能摘一次,并且期间只能向前走,不能回头。
柏拉图于是按照老师说的去做了,结果他两手空空的走出了田地。老师问他为什么摘不到?
他说:“因为只能摘一次,又不能走回头路,期间即使见到最大最金黄的,因为不知前面是否有更好的,所以没有摘。走到前面时,又发觉总不及之前见到的好,原来最大最金黄的麦穗早已错过了。于是我什么也没有摘!”
老师说:这就是“爱情”。
之后有一天柏拉图问他的老师什么是婚姻?老师就叫他先到树林里,砍下一颗全树林里最大最茂盛的,最适合放在家做圣诞树的树。期间同样只能砍一次,以及同样只能向前走,不能回头。
于是柏拉图又照着老师的话去做。今次,他带了一颗普普通通,不是很茂盛,也不算太差的树回来。老师问他:怎么带这颗这么普通的树回来?他说:“有了上一次的经验,当我走到大半路程还两手空空时,看到这颗树也不太差,便砍了下来,免得错过了后,最后有什么也带不回来。”
老师说:“这就是婚姻!”
数学解答
现在我们用数学的角度来讨论这个问题。
假设我们碰到的麦穗有n个,我们用这样的策略来选麦穗,前k个,记住一个最大的麦穗记为d(可能是重量,也可能是体积),然后k+1个开始,只要大于d的,就选择,否则就不选择。
对于某个固定的k,如果最大的麦穗出现在了第i个位置(k<i≤n),要想让他有幸正好被选中,就必须得满足前i-1个麦穗中的最好的麦穗在前k个麦穗里,这有k/(i-1)的可能。考虑所有可能的i,我们便得到了前k个麦穗作为参考,能选中最大麦穗的总概率P(k):
设k/n=x,并且假设n充分大,则上述公式可以改为:
对-x·lnx求导,并令这个导数为0,可以解出x的最优值,它就是欧拉研究的神秘常数的倒数——1/e。
所以k=n/e.
如果你想摘取最大的麦穗,假设有n个麦穗,你应该先将前n/e个麦穗作为参考,然后再k+1个麦穗开始选择比前面k个最大的麦穗即可。
e = 2.718281828459,1/e = 0.36787944117144。
其他例子:
一、一楼到十楼的每层电梯门口都放着一颗钻石,钻石大小不一。你乘坐电梯从一楼到十楼,每层楼电梯门都会打开一次,只能拿一次钻石,问怎样才能拿到最大的一颗。
答案:首先,这个题目说的,并不能完全拿到最大的钻石。但可以保证拿到最大钻石的概率最大。10/e = 3.67,向上取整,得4。则:前四层皆不取,只记下最大的。后面遇到的,只要比前面最大的还大,取之。即可。
二、秘书问题。在机率及博弈论上,秘书问题(类似名称有相亲问题、止步问题、见好就收问题、苏丹的嫁妆问题、挑剔的求婚者问题等)内容是这样的:要聘请一名秘书,有n人来面试。每次面试一人,面试过后便要即时决定聘不聘他,如果当时决定不聘他,他便不会回来。面试时总能清楚了解求职者的适合程度,并能和之前的每个人作比较。问凭什么策略,才使选得到最适合担任秘书的人的机率最大?
转载自原文链接, 如需删除请联系管理员。
原文链接:麦穗理论,又名“秘书问题”(1/e处为最优分割点),转载请注明来源!