s*****a 发帖数: 19 | 1 如果有三个房间,分别有三个人,编号为1、2、3,需要你选出个子最高的人(目测就能
看出来),但是有个条件,当你看完1号房间的人后,你要决定是否看2号房间的人,一
旦看了,就只能选2号房以后的人,既2号或3号,同理,看完2号房,如果想看3号房,就
只能选3了,问题是,使用怎样的策略可以是你选到身高最高的人的概率最大,这个概率
是多少。 | a**********s 发帖数: 588 | 2 问题需要再讲清楚一点
目测能够知道身高的高度? 还是只能比较两个人谁高谁矮?
另外, 身高的分布知道不知道? | f*********r 发帖数: 68 | | a**********s 发帖数: 588 | 4 Don't understand. How?
【在 f*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 0.5, use DP
| f*********r 发帖数: 68 | 5 概率里面的秘书问题, 你可以google一下. 用dp解概率方程
【在 a**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Don't understand. How?
| n******r 发帖数: 1247 | 6 assume 1,2,3 each has 1/3 the probability to be the max
choose the strategy as
check 2 after checking 1, if 2>1, choose 2, else choose 3
the probability of finding the max using this strategy is
P{2>1}*P{2>3|2>1}+P{2<=1}*P{3>1|2<=1}=1/2*2/3+1/2*1/3=1/2
【在 a**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Don't understand. How?
| c****e 发帖数: 3522 | 7 0。7几把?
【在 f*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 0.5, use DP
| c****e 发帖数: 3522 | 8 0。7几把?
就能
,就
概率
【在 s*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果有三个房间,分别有三个人,编号为1、2、3,需要你选出个子最高的人(目测就能 : 看出来),但是有个条件,当你看完1号房间的人后,你要决定是否看2号房间的人,一 : 旦看了,就只能选2号房以后的人,既2号或3号,同理,看完2号房,如果想看3号房,就 : 只能选3了,问题是,使用怎样的策略可以是你选到身高最高的人的概率最大,这个概率 : 是多少。
| g*******y 发帖数: 1930 | 9 这题挺难的呢
分析一下,策略很容易想,但是要算出概率需要用到概率分析的方法
假设从N个房间里面选出最高的人的最佳策略的成功几率是F(N)
第i个房间
a) 如果h[i]不是1...i中的最大值,直接跳到下一个房间
b) 如果h[i]是1...i中的最大值,那么比较:
i/N vs sum of {Prob(剩下的数里面有j个大于i)* F(j)}
如果 i/N 大于后者,那么选i,否则,跳到下一个房间
关键就是怎么算 F(N-i)
假设从1...N个房间里,最终选了第j个房间的人
那么根据以上策略,必然有:
j/N >= 1/(N-j+1) * sum of Prob(F(k), k=1...N-j)
用DP的思路,假设你已经算出来了F(1)...F(N-1)
你只需要扫描j=1...N,即可算出 满足以上条件的一串 j的位置:
j1,j2...jk
于是成功的概率就是:
F(N) = sum of Prob(最大值在jk位置 && j1...jk-1 位置上都不是局部最大) | g*******y 发帖数: 1930 | 10 验证一下,
F(1)=1;
F(2)=1/2;
N=3:
j=1时:
lhs = 1/3
rhs = 1/3*(1+1/2) = 1/2
不选第一间房子
j=2,3时,lhs>rhs,可选
可选的j就是 j1 = 2,j2 = 3
带入公式:
F(N) = sum of Prof(max at jk && j1..jk-1不是"局部"最大)
= 1/3 + 1/3*(1/2) = 1/2
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题挺难的呢 : 分析一下,策略很容易想,但是要算出概率需要用到概率分析的方法 : 假设从N个房间里面选出最高的人的最佳策略的成功几率是F(N) : 第i个房间 : a) 如果h[i]不是1...i中的最大值,直接跳到下一个房间 : b) 如果h[i]是1...i中的最大值,那么比较: : i/N vs sum of {Prob(剩下的数里面有j个大于i)* F(j)} : 如果 i/N 大于后者,那么选i,否则,跳到下一个房间 : 关键就是怎么算 F(N-i) : 假设从1...N个房间里,最终选了第j个房间的人
| l***i 发帖数: 1309 | 11 Strategy
S1: choose person P1. p = 1/3
S2: skip P1, choose the first among P2 and P3 that is higher than P1.
p = p(P2) + p(P3) = 1/3 + 1/6 = 1/2
p(P2) = p(P2 is best among P1,P2)*p(best is in P1,P2) = 1/2*2/3 = 1/3
p(P3) = p(P1 is best among P1,P2)*p(P3 is best in P1,P2,P3) * p(best is in
P1,P2,P3) = 1/2 * 1/3 * 1 = 1/6
S3: skip P1,P2, and choose P3.
p = 1/3 because we have only one choice which is P3. | g*******y 发帖数: 1930 | 12 看你的分析中的S2那步
“choose the first among P2 and P3 that is higher than P1”
如果N>3了,这步是有问题的。
为什么N=3没问题,是因为对于N=2,N=1,最佳的策略都是选择第一个
如果N=4了
S2的时候,你skip了P1,如果P1是最小的,剩下的数里面有3个数大于P1,难道你还是要坚持选“choose the first among P2, P3, P4 that is higher than P1”吗?
PS,尽管题目里面是N=3,不过推广一下题目的要求总是好的~
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Strategy : S1: choose person P1. p = 1/3 : S2: skip P1, choose the first among P2 and P3 that is higher than P1. : p = p(P2) + p(P3) = 1/3 + 1/6 = 1/2 : p(P2) = p(P2 is best among P1,P2)*p(best is in P1,P2) = 1/2*2/3 = 1/3 : p(P3) = p(P1 is best among P1,P2)*p(P3 is best in P1,P2,P3) * p(best is in : P1,P2,P3) = 1/2 * 1/3 * 1 = 1/6 : S3: skip P1,P2, and choose P3. : p = 1/3 because we have only one choice which is P3.
| f*********r 发帖数: 68 | 13
这里有问题, 多算几个F, 估计N=10左右也许更大, 你就会发现错误.
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题挺难的呢 : 分析一下,策略很容易想,但是要算出概率需要用到概率分析的方法 : 假设从N个房间里面选出最高的人的最佳策略的成功几率是F(N) : 第i个房间 : a) 如果h[i]不是1...i中的最大值,直接跳到下一个房间 : b) 如果h[i]是1...i中的最大值,那么比较: : i/N vs sum of {Prob(剩下的数里面有j个大于i)* F(j)} : 如果 i/N 大于后者,那么选i,否则,跳到下一个房间 : 关键就是怎么算 F(N-i) : 假设从1...N个房间里,最终选了第j个房间的人
| g*******y 发帖数: 1930 | 14 好像是有问题,我再想想
改成
i/N vs sum of {Prob(剩下的数中,第一个大于i的数出现在位置j)* F(N-j+1)}
好像就对了?
其中:
Prob(剩下的数中,第一个大于i的数出现在位置j) = i/j*(j-1)
【在 f*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这里有问题, 多算几个F, 估计N=10左右也许更大, 你就会发现错误.
|
|