智游城

标题: 选西瓜 [打印本页]

作者: 老陈 时间: 2019-10-30 03:31
标题: 选西瓜
有N(很多)个西瓜，让你选一个。规则是，拿来一个西瓜，你可以选中，此时选西瓜结束，如果你拒绝这个西瓜，再拿一个西瓜让你选，重复第一个的办法。拿来一个西瓜让你选时你无法知道后面西瓜的大小，可以知道还有多少个西瓜。显然随便选一个，选中最大的西瓜的概率为1/N，采用什么策略可以提高选中最大西瓜的概率？

作者: Howard 时间: 2019-10-31 03:18
这个问题正好看过。回答会导致后面的朋友不愿再思索，但考虑到现在人气不行，本来也未必有人会思考，发于此
最佳策略是放弃前 0.37N 的西瓜，从下一个开始选，只要某瓜比前面见过的都大，就选它。如果一直没有，那就选最后一个。

其中0.37是1/e 也就是0.367879441。得到最大西瓜的概率也是1/e。

此算法可以最大化得到最大西瓜的概率。但得到的西瓜的平均大小期望值并不是最大的，因为并没有考虑第二大、第三大、第四大。。。。的西瓜。

如果要考虑挑到西瓜大小的平均排名最高，则要复杂得多。经过一番人神共愤的论证之后，用最佳方法，当N趋向于无穷时，挑到的西瓜的排名期望值是3.8695

作者: notch 时间: 2019-10-31 08:32

Howard 发表于 2019-10-31 03:18
这个问题正好看过。回答会导致后面的朋友不愿再思索，但考虑到现在人气不行，本来也未必有人会思考，发于此 ...

老陈的问题正好之前也看过答案

很好奇howard题目中的人神共愤的最佳解法

作者: twotu 时间: 2019-10-31 08:56
这个应该跟谈恋爱如何挑选到最佳伴侣的是同一道题吧

作者: Howard 时间: 2019-11-5 02:05

notch 发表于 2019-10-30 18:32
老陈的问题正好之前也看过答案

很好奇howard题目中的人神共愤的最佳解法

这个结果是拒绝前√n （根号n）的西瓜，从下一个开始选比前面都大的

对于大多数n来说，√n < n/e，因此，要选择到期望值最大的西瓜，要比最大化选到最大西瓜的方法提前一些开始选。

论证过程说实在的我还看不懂，想卖弄也没办法

作者: bedok 时间: 2019-11-5 10:55
是否有假定西瓜的大小符合正态分布？

作者: Howard 时间: 2019-11-5 22:13

bedok 发表于 2019-11-4 20:55
是否有假定西瓜的大小符合正态分布？

这个并没有。

1）首先，为了方便起见，论证此问题的过程，假定了是（0，1）上的均匀分布。
如果有100个西瓜，那瓜的大小分别是0.01, 0.02, 0.03... 1.00
N个西瓜则大小分别是1/N, 2/N, 3/N .... 1

2) 大小的分布并不影响计算过程和结果。
我们需要的只是排名。哪怕瓜在某一个区间大小特别集中，在其他的区间比较分散，也还是按照排名而已。从排名上看不出大小属性本身的，只是相对于其他瓜的大小。

作者: bedok 时间: 2019-11-6 01:03

Howard 发表于 2019-11-5 22:13
这个并没有。

1）首先，为了方便起见，论证此问题的过程，假定了是（0，1）上的均匀分布。

如果假定了(0,1)的均匀分布, 那么如果来了一只0.99999998的瓜, 不管它是第几只瓜, 那当然就把它留下了.
如果假定是均匀分布, 且假定范围是(a,b), (a b 未知). 那么从前面n只瓜的采样, 也可以给出对a b的估计, 从而依据这个估计来求解
如果假定是正态分布, 均值和标准差未知. 那么从前面n只瓜的采样, 也可以给出对均值和标准差的估计, 从而依据这个估计来求解
由此可见分布的假定还是很重要的

作者: Howard 时间: 2019-11-6 02:57
此言甚是有理。我的均匀分布说法不正确，应该是未知的分布，随机的排序。

然而在生活中这种理想随机难以得到。比如说挑西瓜，我们都知道一个西瓜也就是五斤到20斤之间。看到一个40斤的，那不要再看了就选它。

再比如中文网络流行的“选对象”，人群中异性的平均分布大家基本上也有个估计，看到一个貌如林志玲，脾气又好，又会做家务的姑娘，那不用说也是top 1%，再遇到比她好的已经不太可能了

英文文献的原问题是选秘书。秘书的能力也有个生活常识即可判断的上下限。打字500每分钟，非常有条理，还随叫随到，还能提出建设性意见，这样的哪怕是第一个面试也得留下

要想找出一个纯未知分布的，还真不容易

还有个问题就是样本一大，基本就都是正态分布了，无论是何种性质的问题

作者: bedok 时间: 2019-11-6 10:40

Howard 发表于 2019-11-6 02:57
此言甚是有理。我的均匀分布说法不正确，应该是未知的分布，随机的排序。

秘书的话, 其实可以让人回去等消息......
所以说选对象可能是最贴切的. 过去了的就真的只能过去了. 但是这个也说不定哎......旧情复燃也有可能.....

回到题目, 假定正态分布, 总共100只

举例说明: 当拿到第30只的时候, 均值是10斤, 标准差1斤. 计算得出大约12.3斤就可以收手了. 否则就拿第31只.重新计算均值和标准差.再来一遍.
火花的方法其实不错, 如果不能假定分布, 1/e大概是个不错的办法.

作者: notch 时间: 2019-11-7 10:45

bedok 发表于 2019-11-6 10:40
秘书的话, 其实可以让人回去等消息......
所以说选对象可能是最贴切的. 过去了的就真的只能过去了. 但是 ...

这个方法的问题是你应该在什么时候来计算均值和方差？
第10个？第20个？第30个？

作者: bedok 时间: 2019-11-8 00:45

notch 发表于 2019-11-7 10:45
这个方法的问题是你应该在什么时候来计算均值和方差？
第10个？第20个？第30个？
...

每次拿完瓜都计算一次

作者: notch 时间: 2019-11-12 13:32

bedok 发表于 2019-11-8 00:45
每次拿完瓜都计算一次

前几次样本量太少，平均值和sigma算出来完全不能体现整个的分布。

作者: bedok 时间: 2019-11-13 06:52

notch 发表于 2019-11-12 13:32
前几次样本量太少，平均值和sigma算出来完全不能体现整个的分布。

我觉得不会差太远, 当样本量少的时候, 方差的估计会比较大

欢迎光临智游城 (http://zhiyoucheng.co/)