麦穗理论

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《麦穗理论》，欢迎阅读！

麦穗理论

来自数学博客

故事

有一天，柏拉图问老师苏个拉底什么是爱情? 老师就让他先到麦田里去，摘一颗全麦田里最大最金黄的麦穗来。期间只能摘一次，并且期间只能向前走，不能回头。

柏拉图于是按照老师说的去做了，结果他两手空空的走出了田地。老师问他为什么摘不到？

他说：“因为只能摘一次，又不能走回头路，期间即使见到最大最金黄的，因为不知前面是否有更好的，所以没有摘。走到前面时，又发觉总不及之前见到的好，原来最大最金黄的麦穗早已错过了。于是我什么也没有摘！” 老师说：这就是“爱情”



之后有一天柏拉图问他的老师什么是婚姻？老师就叫他先到树林里，砍下一颗全树林里最大最茂盛的，最适合放在家做圣诞树的树。期间同样只能砍一次，以及同样只能向前走，不能回头。

于是柏拉图又照着老师的话去做。今次，他带了一颗普普通通，不是很茂盛，也不算太差的树回来。老师问他：怎么带这颗这么普通的树回来？他说：“有了上一次的经验，当我走到大半路程还两手空空时，看到这颗树也不太差，便砍了下来，免得错过了后，最后有什么也带不回来。”

老师说：“这就是婚姻！”

数学解

现在我们用数学的角度来讨论这个问题。

假设我们碰到的麦穗有n个，我们用这样的策略来选麦穗，前k个，记住一个最大的麦穗记为d（可能是重量，也可能是体积），然后k+1个开始，只要大于d的，就选择，否则就不选择。



对于某个固定的 k，如果最大的麦穗出现在了第 i 个位置（k < i ≤ n），要想让他有幸正好被 选中，就必须得满足前 i-1 个麦穗中的最好的麦穗在前 k


个麦穗里，这有 k/(i-1) 的可能。考虑所有可能的 i，我们便得到了前 k 个麦穗作为参考，能选中最大麦穗的总概率 P(k)：

$P(k)=\backslash sum\_\{i=k+1\}^\{n\}\backslash frac\{1\}\{n\}\backslash frac\{k\}\{i-1\}=\backslash frac\{k\}\{n\}\backslash sum\_\{$i=k+1}^{n}\frac{1}{i-1}

设 k/n=x ，并且假设 n 充分大，则上述公式可以改为： $P(k)=x\backslash int\_\{x\}^\{1\}\backslash frac\{1\}\{t\}dt=-x\; ln(x)$

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

如果你想摘取最大的麦穗，假设有 n 个麦穗，你应该先将前 n/e 个麦穗作为参考，然后再k+1个麦穗开始选择比前面k个最大的麦穗即可。

本文来源：https://www.wddqxz.cn/3419d3a50029bd64783e2cd7.html