鑰匙丟在家裡的概率是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。

前提是你的鑰匙是可以找到的，如果沒有這個前提，你的假設條件都不成立。

所以，這個題目應該有一個前提，就是假設你的鑰匙是可以找到的，然後，才可以用概率去估計。

推薦閱讀：
相关文章