假設(shè)你要開車從A到B，橫豎兩個(gè)方向都要穿過多個(gè)路口，怎么走最快？
- 直來(lái)直去，走個(gè)大折線，簡(jiǎn)單；
- 碎步溜，走小折線，永遠(yuǎn)向著目標(biāo)；
- 見機(jī)行事，見綠燈往前沖，見紅燈右轉(zhuǎn)。
直覺上，你是不是會(huì)選3？
模型
為了便于分析，我們要建立一個(gè)簡(jiǎn)化的模型。
- 從A到B，是一個(gè)8x8的棋盤道路；
- 每個(gè)路口的紅燈、綠燈都是1分鐘；
- 不同路口的紅綠燈沒有關(guān)聯(lián)，你會(huì)隨機(jī)地碰到紅燈或綠燈；
- 每個(gè)路口都可以左轉(zhuǎn)/直行/右轉(zhuǎn)（忽略變道選擇的細(xì)節(jié)）；
- 不糾結(jié)起步、剎車，轉(zhuǎn)彎、直行的各種時(shí)間差異。
問題，按怎樣的路線開車總時(shí)間最短？
數(shù)學(xué)分析
首先，走大折線肯定慢。比如走綠線要過14個(gè)路口，概率上會(huì)碰到7個(gè)紅燈；而走藍(lán)線也是14個(gè)路口，加1個(gè)左轉(zhuǎn)彎，概率上是7.5個(gè)紅燈。還有比這更慢的嗎？——顯然沒有。
其實(shí)這個(gè)問題可以用遞歸的方法解決。如圖，
對(duì)于一階最優(yōu)解S1就是路線R1，等待時(shí)間是0個(gè)紅燈。
S1 = R1 = 0
對(duì)于二階：
- R2A有一個(gè)左轉(zhuǎn)，平均0.5個(gè)紅燈；
- R2B表示如果碰到綠燈先直行，其結(jié)果也是0.5個(gè)紅燈，并不會(huì)比R2A更快；
- R2C顯然不行，1.5個(gè)紅燈。所以，
S2 = R2A = 0.5
對(duì)于三階（及更高階）：
- R3 = 0.5 + R2A；
- 或：R2B + 0.5 （如果先碰到綠燈）；
- 或：R2C + 0.5 （出發(fā)時(shí)就先右轉(zhuǎn)）太慢了，直接忽略。
遞歸的方式，實(shí)際上是可以窮舉的。每一次遞歸只有3種變化。所以：
- S(1) = 0
- S(n) = 0.5 + S(n-1) = (n-1)*0.5
8階就是3.5個(gè)紅燈。每個(gè)紅燈平均等待30秒，所以最優(yōu)策略的期望等待時(shí)間105秒。
新問題
按照小折線（黃色的路線），最多等7個(gè)紅燈，最少0個(gè)紅燈，所以平均算3.5個(gè)紅燈。沒錯(cuò)吧？
每個(gè)紅燈最多等60秒，最少等0秒（理論上是0.00...01秒才算紅燈），所以平均算30秒。沒錯(cuò)吧？
這樣算下來(lái)，總體上平均等待時(shí)間30 * 3.5 = 105 秒，這個(gè)也沒錯(cuò)吧？
但換個(gè)角度，總體上最少等0秒，最多等7*60=420秒，中間值是210秒，這個(gè)也沒錯(cuò)吧？
但平均值是105秒。
這說明，等待的時(shí)間不是對(duì)稱的分布？
感覺有點(diǎn)怪。。
模擬實(shí)驗(yàn)
蘿卜頭實(shí)驗(yàn)室不能空談，一切以實(shí)驗(yàn)為準(zhǔn)。
本來(lái)應(yīng)該寫段程序模擬的。但Excel很強(qiáng)大了，就用Excel吧。
每一行代表一次實(shí)驗(yàn)。
一次實(shí)驗(yàn)包括：
- 7個(gè)路口分別是碰到紅燈還是綠燈，以及每個(gè)紅燈的等待時(shí)間。
- 每個(gè)路口是否會(huì)碰到紅燈，公式：=INT(RAND()*2)，0表示綠燈，1表示紅燈；
- 每個(gè)路口等待的時(shí)間：=RAND()*60
- 總共等待的紅燈數(shù)：=SUM(A2:G2)
- 總共等待的時(shí)間：=SUMPRODUCT(A2:G2, H2:N2)
因?yàn)槎际请S機(jī)數(shù)，這個(gè)表格每次打開都不一樣，復(fù)制單元格到看的數(shù)值也是不一樣的。
用條件格式把這個(gè)表格弄得更易讀（花哨）一點(diǎn)。如前所述，數(shù)據(jù)不會(huì)和前一張圖相同。
最后兩列是總計(jì)：紅色深淺代表紅燈多少；藍(lán)色條代表等待時(shí)間。
這兩列的直方圖反映了分布狀況。下圖代表5000次實(shí)驗(yàn)的結(jié)果。
下圖代表1048575次實(shí)驗(yàn)的結(jié)果。
可以看出，
- 平均碰到的紅燈確實(shí)是3.5個(gè)；
- 等待時(shí)間確實(shí)不是對(duì)稱分布。其峰值和均值都是105秒。但0附近和55~60之間的峰值有點(diǎn)奇怪（試了幾次都是這樣）。
順便說一句，1048576（=1024*1024）是Excel表格的最大行數(shù)。操作這么大的表格對(duì)電腦是個(gè)考驗(yàn)。
結(jié)語(yǔ)
對(duì)于縱橫兩個(gè)方向路口數(shù)相同的（NxN棋盤格）目的地，交替左轉(zhuǎn)和右轉(zhuǎn)的小折線是最快的，等紅燈的總時(shí)間只有大折線的一半。
如果縱橫兩個(gè)方向路口數(shù)不相同呢？——可以轉(zhuǎn)化成直線段+NxN棋盤格的模式。
最后，實(shí)際開車的因素比這復(fù)雜得多。這只是個(gè)簡(jiǎn)化模型加Excel的小把戲。僅供參考。
安全第一。
