钥匙丢在家里的概率是30%，丢在学校的概率是70%；

如果钥匙确实丢在学校，那么每当我在学校寻找一个小时，找到钥匙的概率为40%；

如果钥匙确实丢在家里，那么每当我在家里寻找一个小时，找到钥匙的概率为80%；

假设家里和学校的距离非常近，交通所需要的时间可以忽略不计。那么，我应该用什么策略寻找钥匙才能让我「最快」地找到钥匙？

【如果不满足于「找一个小时找到的概率为40%」这种不合实际的限制，可以用指数分布代替，比如连续搜索x长度的时间时找到钥匙的概率为 P(x)=1-e^{-lambda x} ；但是在这种情况下必须增加条件，在学校与家之间每进行一次移动都需要消耗一定的时间

如果不满足于这个题目模型，那么考虑以下的版本：

假设钥匙丢在了一条小路上，这条路用 [0,1] 表示；由于地形的影响，这条路上的能见度处处不同，用 varphi(x) 表示；设 s:mathbb R^+ ightarrow[0,1] 是一条行进路线路线，满足以下三个条件：

1、 s 处处连续

2、 s 的不可导点无处稠密3、 |s(t+0)|=|s(t-0)| 恒成立，意即速度的绝对值不会发生突变

现在，假设小明沿著曲线 s 行进，而钥匙丢在了 x_0 处，那么若 s(t_0)=x_0 并且曲线 s 在 [t_0-varepsilon,t_0+varepsilon ] 内只经过 x_0 一次，则小明在这段时间内找到钥匙的概率为 1-e^{-varphi(s(t_0))/|s(t_0)|}

现在，假设钥匙丢在这条路上的某处的概率密度函数为 f(x) ，问按照什么样的行进路线 s 寻找钥匙可以令找到钥匙所需的时间期望值最小？（为了确保解的存在性，可以要求 |s|<M ）

以上的函数 varphi,f 均可视为连续函数

这个题只能给出一个最速寻找法，但是存在一直找不到的可能。

在家里条件概率

已经在家里找了m次，在学校找了n次，实际在家里的概率p_home

为 函数p_home(m,n,p,q,P0,Q0)

p_home=P0*(1-p)^m/[P0*(1-p)^m+Q0*(1-q)^n]

上式中p为在家搜寻的成功率=80%

q为在家搜寻的成功率=40%

P0为初始的在家概率30%

Q0为初始的在学校概率70%

最优选择

那么在家找，还是在学校找呢？

p_home*p&>(1-p_home)*q，就在家，否则去学校

第一步，p_home=30%，30%*80%&<70%*40%,去学校

第二步……

按此最快方式找的，预期要3.1856次找到。

这里可以看到些规律，每次回家找，没找到，都要到学校再找个3~4次。这是因为家里找到成功率达到80%，如果没找到，说明不在家里的概率大大增加了。而学校找到的概率60%，需要找好几次才抵得上家里的效果。Ln(0.2)/Ln(0.6)~=3.1。

如果允许不是整个小时的搜寻，就有点像复利推导自然对数的过程了。……，对我来说太复杂了。

Update 2019-01-04：完善最优解的证明。

@傻子.傻问题杀手 的找法是最优解，首先注意到：

  1. 如果前两次在不同的地方找钥匙，那么应该优先在更容易找到的地方（即：钥匙丢在此地的概率与在此地找到钥匙的概率之积较高）找钥匙，否则不是最优解。

（找一个小时钥匙称为找一次）

用 p_h,p_s,q_h,q_s 分别表示钥匙在家的概率、钥匙在学校的概率、当钥匙在家时在家找一次钥匙成功的概率、当钥匙在学校时在学校找一次钥匙成功的概率。

假设 p_hq_h>p_sq_s，但我前两次先在学校找钥匙再在家找钥匙，那么将前两次找钥匙的顺序交换（以后的找钥匙策略不变），找钥匙的期望时间会减少。理由如下：

记 X 为找钥匙花费的次数，则有等式

E(X)=P(X>0)+P(X>1)+P(X>2)+P(X>3)+cdots

其中 P(X>k) 为前 k 次没找到钥匙的概率。

注意到：若在家寻找 a 次钥匙，在学校寻找 b 次钥匙，则没找到钥匙的概率等于 p_h(1-q_h)^a+p_s(1-q_s)^b，它与寻找钥匙的次序无关。现在考虑将前两次找钥匙的地点交换，容易看出只有 P(X>1) 改变了，其他的 P(X>k)(k<br /> e1) 值没有变化。

如果先在学校找钥匙再在家找钥匙，则 P(X>1)=1-p_sq_s；交换次序之后， P(X>1) 变成了 1-p_hq_h，比原来的值要小，即 E(X) 变小。

2. 如果第一次在家找钥匙没找到，那么此时钥匙在家的概率比初始时低，在学校的概率比初始时高；反之（如果第一次在学校找钥匙没找到）则相反。

显然。

结合这两点可以得到下面的结论：

3. 第一次找钥匙应该优先在更容易找到的地方找钥匙，否则不是最优解。

假设 p_hq_h>p_sq_s，但我第一次在学校找钥匙，那么我必然是先在学校找 k 次钥匙，然后下一次在家找钥匙（如果始终在学校找钥匙，显然找钥匙的期望时间为正无穷）。

当我在学校找 k-1 次钥匙之后，根据第 2 条可知此时钥匙在家的概率比初始时高，在学校的概率比初始时低，因此关系式 p_hq_h>p_sq_s 仍然成立。而接下来两次找钥匙分别是在学校和在家，根据第 1 条可知交换它们得到的解更优，此时策略变成了先在学校找 k-1 次钥匙，再在家找一次钥匙，再在学校找一次钥匙。

如果 k-1 仍然是正整数，重复上述操作还能得到更优的解，直到「在家找钥匙」的操作换到了第一次，即第一次是在家找钥匙为止。

这就说明了「优先在更容易找到的地方找钥匙」如果是最优解，则是唯一可行的最优解。

为了证明该策略的确是最优解，记该策略为策略 A，相应的期望寻找时间记为 E_A(X)。先证明下面的引理：

4. 对任意正实数 varepsilon，总存在正整数 n，使得对任意策略 B，只要该策略的前 n 次寻找地点与策略 A 相同，就有 E_B(X)>E_A(X)-varepsilon。

证明：注意到

E_A(X)=sum_{k=0}^infty P_A(X>k),

先固定正整数 n ，假设策略 B 的前 n 次寻找地点与策略 A 相同，则有

P_B(X>k)=P_A(X>k),k=0,1,cdots,n,

因此

egin{align} E_B(X)=sum_{k=0}^infty P_B(X>k) \ =sum_{k=0}^nP_B(X>k)+sum_{k=n+1}^infty P_B(X>k) \ gesum_{k=0}^nP_A(X>k). end{align}

又因为 E_A(X)=lim_{n ightarrowinfty}sum_{k=0}^nP_A(X>k)，可以取正整数 n 使得

|E_A(X)-sum_{k=0}^nP_A(X>k)|<varepsilon,

从而 E_B(X)gesum_{k=0}^nP_A(X>k)>E_A(X)-varepsilon. 证明完毕。

现在假设策略 B 比策略 A 更优，即 E_B(X)<E_A(X) 。取 varepsilon=E_A(X)-E_B(X)，则能找到满足上述引理的正整数 n。因为策略 B 不可能只在家找有限次钥匙，或者只在学校找有限次钥匙（否则期望值会发散），根据第 3 条提供的方法，可以经过有限次交换使得策略 B 变成策略 C，它的前 n 次寻找地点与策略 A 相同，并且优于策略 B。从而

E_C(X)le E_B(X)=E_A(X)-varepsilon,

这与引理矛盾。至此可以断定「优先在更容易找到的地方找钥匙」就是最优解。

鄙人天资愚钝，不善于思考。但是终于想明白了，还是 @傻子.傻问题杀手说得对。

问题描述

这个问题中有三个量：

  • p：钥匙在家的概率
  • a：如果钥匙在家，在家找一次能够找到的概率
  • b：如果钥匙在学校，在学校找一次能够找到的概率

其中，a、b为常量，p为变数。p会随著每次寻找而变化。

状态转移

假如第一次在家里找，结果没有找到，钥匙依旧在家的概率为 p_1=frac{p imes(1-a)}{1-p imes a} ,此时钥匙在学校的概率为 1-p_1 ；如果第一次在学校找，结果没找到，钥匙依旧在家的概率为 p_1=frac{p}{1-(1-p) imes b}

解决思路

定义 f(p) 表示最优决策下找到钥匙所需要的期望次数。

则：

f(p)=min{cost_{home},cost_{school}}\ cost_{home}表示第一次去家里找，期望花费步数：\ cost_{home}=canfind imes1+(1-canfind) imes [1+f(p_1)]\ cost_{school}表示第一次去学校找，期望花费步数：\ cost_{school}=canfind imes1+(1-canfind) imes [1+f(p_1)]

其中canfind表示能够找到的概率， p_1 表示经过一次寻找之后钥匙在家的概率。如果在家里找到了，那么只需要一步就能找到钥匙；如果没有找到，那么需要 1+f(p_1) 步才能找到钥匙。

  • 贪心法应该是对的

根据 p imes a>(1-p) imes b 来决定去家里找还是学校找。

假如寻找次数为16步，那么所有的寻找序列构成一个深度为16的二叉树。从根节点到叶子节点的路径就表示一个决策。每个结点都有一个数字f(node)表示该结点的找到钥匙的期望寻找次数。当前节点的期望寻找次数依赖于它的两个儿子（分别对应去家里找和去学校找的期望寻找次数）中的期望寻找次数较小者。按照这个方法，暴力枚举整个满二叉树上的决策，发现最终得到的决策路径和贪心法找大的决策路径是一致的。

结论

最优路径是：school home school school school home school school school home school school school home school school school home school school school school home school school school home school school school home school school school home school school school home school school school home school school school home school school school school home school school school home school school school home school school school home school school school home school school school home school school school school home school school school home school school school home school school school home school school school home school school school home school school school

期望寻找次数为：3.1857095316916766

下图表示钥匙在家的概率随寻找次数的变化。

期望寻找次数随著钥匙在家的概率p的变化曲线，也就是f(p)的函数曲线。这条曲线的最大值对应的点为pa=(1-p)b,p=b/(a+b)

p = 0.3 # 钥匙在家的概率
a = 0.8 # 在家找到的概率
b = 0.4 # 在学校找到的概率

def solve(p, c):
# 钥匙在家的概率为p，返回最优决策、期望找到钥匙所花费的步数
if c == 0:
return [], max(1 / a, 1 / b) # 如果最后没有找到，期望步数为无穷多步
if p * a &> (1 - p) * b:
# 如果去家里找，找到的概率
canfind = p * a # 在家里找能够找到的概率
still_home = p * (1 - a) / (1 - p * a) # 钥匙依旧在家的概率
home_choice, step = solve(still_home, c - 1) # 如果没找到，那么接下来可以找到的期望步数
ifhome = 1 * canfind + (1 + step) * (1 - canfind) # 如果去家里找，期望找到的步数
return [(home, p)] + home_choice, ifhome
else:
# 如果去学校找
canfind = (1 - p) * b # 找到的概率
still_school = (1 - p) * (1 - b) / (1 - canfind) # 没有找到，但是依旧在学校的概率
still_home = 1 - still_school # 钥匙在家的概率
school_choice, step = solve(still_home, c - 1)
ifschool = canfind + (1 + step) * (1 - canfind)
# 选取两个儿子中期望步数较小者
ans = [(school, p)] + school_choice, ifschool
return ans

c = 100
steps, prob = solve(p, c)
print( .join(i[0] for i in steps))
print(prob)
import pylab as plt

ps = [i[1] for i in steps]
plt.plot(ps)
plt.xlabel("step")
plt.ylabel("p")
plt.show()
import numpy as np
xs = np.linspace(0, 1, 100)
ps = [solve(i, c)[1] for i in xs]
plt.plot(xs, ps)
plt.xlabel("p")
plt.ylabel("step")
plt.show()

说明：如果超过有限步依旧没有找到，这时就可以瞎编一个数字了，因为还没找到的概率实在太低了，但是瞎编的这个数字也不能太大（因为找不到的概率是很小的）。

===================================

f(p) 函数表示钥匙在家时，期望寻找次数。这个函数表达式为

f(p)=min{1+(1-pa)f(frac{p-pa} { 1 - pa}),1+(1-b+pb)f(frac{p}{1-b+pb})}

根据贪心法（若不是此问题的具体情境，很难看出上式可以转化为条件函数）可以化简此式：

贪心条件为 pacirc(1-p)b ，也就是 pcirc frac{b}{a+b}

这个公式等价于

f(p)= egin{cases} 1+(1-pa)f(frac{p-pa} { 1 - pa}) 当p>frac{b}{a+b} \ 1+(1-b+pb)f(frac{p}{1-b+pb}) 当plefrac{b}{a+b}\ end{cases}

其中，a、b为常量，p取值范围(0,1)

这个解析式是否能够进一步化简呢？

起码有个寻找时间限度吧，最快这个目的条件太奇怪了，因为在非极限时间下，找到钥匙的概率不为1，因此找不到这个最快时间，当然找不到最优策略。而每个时间限度下，找钥匙最大概率不一定相同。可以改为，n小时内找到钥匙的最大概率以及寻找策略;找到概率大于p时至少所花时间。否则，结论是散列的，1h,概率x1%，策略y1；2h,概率x2%，策略y2；……；nh,概率xn%，策略yn。

前提是你的钥匙是可以找到的，如果没有这个前提，你的假设条件都不成立。

所以，这个题目应该有一个前提，就是假设你的钥匙是可以找到的，然后，才可以用概率去估计。

推荐阅读：
相关文章