燒腦題~最佳路徑選擇？

02-18

看到一道題，拿不太准，放上來大家討論討論：
如圖一，要從A到B（2米），假設小明蒙眼出發，假設小明蒙眼也能走任意方向的直線，假設小明很奇怪地堅持要走10次A到B。現在每次出發前，有50%的幾率（擲硬幣決定）出現一堵牆，垂直於路線，長2米，如圖二。那麼小明應該如何規劃，使得自己走的路徑最短？

Optiver的題？樓主準備套答案投optiver 嗎哈？

我覺得就是求最小化期望路徑，不用想複雜了。

圖二的牆上面取一點，朝著他走，記那個點離牆與直線路徑交叉的距離為x，那麼期望的路徑距離就是一個關於x的函數，形式如下：

$1/2 imes(2sqrt{1+x^2}) + 1/2 imes (sqrt{1+x^2} + sqrt{2}+(1-x))$

該函數圖像如下：

在 $x = sqrt{2}/4$ 取到最小值

雖然這題已經過去很久了，而且 @bh lin 樓上的題已經給出一個很標準的答案了，但是我個人認為答案還可以解釋的更好一些。

我覺得就是求最小化期望路徑，不用想複雜了。

圖二的牆上面取一點，朝著他走，記那個點離牆與直線路徑交叉的距離為x，那麼期望的路徑距離就是一個關於x的函數，形式如下：
該函數圖像如下：
在取到最小值

首先在我們寫下函數時，我們已經默認了以下最佳策略一定產生在以下跟x有關的策略之中。

即在紅線上半部分取一個標記X，高度為x,走路策略為從A走到X，然後如果沒牆則直接再走到B，

有牆則走到C繞過牆再直接走到B。

如下圖

之後的就不用我說了，找期望值而已。

雖然這個前提是正確的，但是並不是顯而易見的，我個人認為幾步的證明還是必要的。

所以我這個回答主要是證明這個這個前提。

先把AB的垂直平分線叫做分界線吧。

小明要從A走到B肯定要經過分界線，因為小明的路線是連續的....

假設存在一個最簡的策略：

1）這條策略的移動路線要接觸紅線（注意，紅線是有長度的，但是分界線是無限長的，不能弄混）

證明：用反證法，假如不經紅線，但是因為必經分界線，那麼假設那條最佳策略交分界線於某點Y，那麼明顯最佳策略是A-Y-B,長於A-C-B。產生了悖論。證明結束。

2）如果這條策略接觸紅線於X，那麼上面所述策略就很明顯了

證明：A到X必然是直線最短，X到B如果沒牆則走直線，有牆則先到C再走直線到B。

完。有了這個前提後，那麼題主可以痛快的用上述函數了，然後在[0,1]中間取函數最大值即可，求導和畫圖都可以。

沒看懂→_→ 按照我的理解垂直向上或下走，出現牆就走向b走沒出現就放棄哈哈

1.蒙眼走，怎麼知道A，B到了，應該不是兩個點，也是兩條垂直AB點的牆，撞到牆就算到了。

2.要走最短距離，只能控制角度了，0~45。

3.過程中，是否假設知道當前走了多遠和角度？