用高等數學清掃馬路能省多少錢

七君

大家有沒有想過，平時路上的灑水車、鏟雪車是怎么規劃行車路線的呢？

有人會說，這還不簡單，哪兒沒有跑過就去跑一遍不就行了。這種方法的確能保證所有的道路都被打掃了，但是車子可能會在某幾段馬路上重復開，損失燃油和時間。

掃馬路車、灑水車、鏟雪車這類問題在數學上屬于“中國郵差問題”，早在20世紀70年代就有了靠譜的解法。

這還要從1962年說起。當時，毛主席鼓勵科學家們用科學解決日常生活中遇到的問題。我國數學家管梅谷就想到了這樣一個問題：一個郵差走遍每條街道去送信，最短路徑應該是什么樣的？后來，美國數學家AlanJ. Go l dman把這個問題命名為“中國郵差問題”。

到了1973年，加拿大滑鐵盧大學的數學家Jack Edmonds和IBM研究院的計算機科學家Ellis L. Johnson提出了一個至今無人超越的有效算法。他們的算法要涉及300年前的一個人，那就是歐拉。

其實，歐拉在1735年就研究過一個和管梅谷類似的問題——七橋問題，并得到了一些重要的結論。

七橋問題和我們小時候玩的一筆畫的益智問題類似：在普魯士的柯尼斯堡有兩個小島，兩個小島和附近一共有7座橋連通?，F在問題來了，怎樣規劃路線才能恰好經過每一座橋一次？

第二年，歐拉發表了一篇論文，證明七橋問題不可解，原因是他給出了能解的一般條件，那就是每塊地都必須有偶數座橋，而七橋問題不符合這種情況。這類問題在數學上發展成了圖論和拓撲學。而因為歐拉的開創性貢獻，能夠一筆畫的圖被叫作歐拉圖，能一筆畫的路徑被叫作歐拉路徑。

七橋問題等價于下面這個圖形。歐拉證明，只有當奇頂點的數量等于0或2時，才存在一筆畫。七橋問題的奇頂點（藍點）的數量等于4，因此無法一筆畫。

歐拉還證明了一張圖能一筆畫的一般情況：奇頂點（也就是邊的數量是奇數的頂點）的數量等于0或2。所以按照歐拉證明的定理，中文的“串”就可以一筆寫成，因為它的奇頂點只有最上面和最下面兩個。

把歐拉證明的結論推廣到中國郵差問題的情況，最難搞定的是奇數分叉的道路，遇到三岔路口、五岔路口，走回頭路幾乎是必然的。

所以Edmo n ds他們的算法是，把奇數路口拎出來單獨算，找到這些路口間的最短路徑；而偶數岔路之間必然存在只走一次的方法，最后把兩部分拼起來就可以了。但是呢，實際生活中掃馬路、灑水和鏟雪要比這復雜得多。比如，高速公路的整潔對司機的生命財產安全更重要，所以要早點清掃完畢；一些路段是單行線，或者對大型車輛限行。此外，“郵差”也不止一個人，清潔車之間的交接班也要考慮在內。因此在現實生活中，“中國郵差問題”很難找到最優策略，這也是為什么一開始Edmonds的算法沒有得到廣泛應用。

隨著計算機技術的進步，一些數學家開始嘗試把中國郵差問題應用到日常生活中。比如，明尼蘇達大學的數學教授Peh Ng就曾用圖論的思想幫明州莫里斯市政府規劃冬季的鏟雪線路。

而從2001年開始，北美的一些大城市就開始用比較成熟的軟件，如ArcGIS來規劃鏟雪車的行車路徑。這些軟件一般會把一大塊城市交通網分割成一小塊一小塊的，然后分別再進行計算。比如，多倫多在用圖論原理對鏟雪線路進行規劃后，鏟雪費用比之前減少了三分之一，每年節省了大約300萬美元（約合人民幣2000萬元）。

除了道路養護，中國郵差問題的算法在很多領域還有應用。比如，在交互設計時，中國郵差問題就被用于終端產品的可用性檢測。舉個例子，一個手機被制造出來以后，手機制造商想要看看每個功能是不是和名稱相符。比如，按下主鍵，點開“設置”，再點開“網絡”，是不是真的會出現網絡設定功能。

因為手機的功能很復雜，不同功能之間形成的網絡要怎樣才能有效地走個遍，這個問題有時連制造商也搞不太明白。1996年諾基亞出的2110的菜單有88個項目，一共有273種操作。如果隨便按，可能一些菜單永遠也不會得到檢測。但是利用中國郵差問題的算法就能規劃測試路徑和計算步驟數量了：最少只需要按594次鍵盤按鈕，就可以把所有的菜單和功能都過一遍。

//摘自把科學帶回家微信公眾號，本刊有刪節/