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 的大作中提到】
: 0.5, use DP
| f*********r
发帖数: 68 | 5 概率里面的秘书问题, 你可以google一下. 用dp解概率方程
【在 a**********s 的大作中提到】
: 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 的大作中提到】
: Don't understand. How?
| c****e
发帖数: 3522 | 7 0。7几把？
【在 f*********r 的大作中提到】
: 0.5, use DP
| c****e
发帖数: 3522 | 8 0。7几把？
就能
，就
概率
【在 s*****a 的大作中提到】
: 如果有三个房间，分别有三个人，编号为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 的大作中提到】
: 这题挺难的呢
: 分析一下，策略很容易想，但是要算出概率需要用到概率分析的方法
: 假设从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 的大作中提到】
: 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 的大作中提到】
: 这题挺难的呢
: 分析一下，策略很容易想，但是要算出概率需要用到概率分析的方法
: 假设从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 的大作中提到】
:
: 这里有问题, 多算几个F, 估计N=10左右也许更大, 你就会发现错误.
|
|
