用高等數學清掃馬路

曉昀

: l" V. C# X3 T( X/ p
: f- m# h, A* z

5 Q" i0 c; S9 c6 ?7 D/ `8 V% B

      有人會說，這還不簡單，哪兒沒有跑過就去跑一遍不就行了嘛。

      這種方法的確能保證所有的道路都被打掃了，但是車子可能會在某幾段馬路上重復開，損失燃油和時間。

3 z/ s/ U- O3 P5 H$ {% F

     北美的一個大城市多倫多在好好用數學規劃之前，每年就白白多花了3百萬美金的冤枉錢。
) `8 C) l5 D- s* c7 E

3 b& L0 s+ P+ z7 j1 z$ I' f

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

: Z( ?! \. b4 _1 w8 ~3 Y

     事情還要從1962年說起。當時，毛主席鼓勵科學家們用科學解決人民日常生活中遇到的問題。

     我國數學家管梅谷就想到了這樣一個問題：一個郵差走遍每條街道去送信，最短路徑應該是什么樣的？

     后來，美國國家標準技術研究所的數學家 Alan J. Goldman 把這個問題命名為“中國郵差問題”。

, t$ K4 ~& U" \& o2 `

  C- \! J( B2 t9 F% W7 A0 ^* P

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

, M2 |7 M. I; k  {: m4 K1 S

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

七橋問題 圖片來源：wikipedia

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

5 Q' X1 {5 J, L+ ?  a: U% T

       第二年，歐拉發了一篇論文，證明七橋問題不可解，原因是他給出了能解的一般條件，那就是每塊地都必須有偶數座橋，而七橋問題不符合這種情況。

* U% |: F' z& s" ~4 R2 _, U9 i1 r5 d

      后來，這類問題在數學上發展成了圖論和拓撲學。而因為歐拉的開創性貢獻，能夠一筆畫的圖被叫做歐拉圖，一筆畫的路徑被叫做歐拉路徑。

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

0 |: R) B2 ~% w( s! ^, S7 E2 o

       歐拉還證明了一張圖能一筆畫的一般情況：奇頂點（也就是邊的數量是奇數的頂點）的數量等于0或2。

       所以按照歐拉證明的定理，中文的“串”就可以一筆寫成，因為它的奇頂點只有最上面和最下面一共兩個。

; R7 W* u/ ~" x) i% D) p0 X

串的奇頂點有2個（最上和最下），因此可以一筆畫。

$ M0 ^+ k; N* N! h) w5 I

       下面這個德國兒童的傳統娛樂項目——Haus vom Nikolaus puzzle （圣尼古拉房屋）也可以一筆畫——

! q/ U8 l5 t. h( \6 F

       順便說一下，圣尼古拉房屋有44種解法。

. y. B. W0 N+ M) z

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

      所以 Edmonds 他們的算法是，把奇數路口拎出來單獨算，找到這些路口間的最短路徑；而偶數岔路之間必然存在只走一次的方法，最后把兩部分拼起來就可以了。

       但是呢，實際生活中掃馬路、灑水和鏟雪要比這復雜得多。

       比如，高速公路的整潔對司機的生命財產安全更重要，所以要早點清掃完畢；一些路段是單行線，或者對大型車輛限行。此外，“郵差”也不只一個人，而且不能無限“肝”活，清潔車之間的交接班也要考慮在內。

1 ]8 D7 [5 P: G( h# s$ O5 C3 ^

       因此在現實生活中，中國郵差問題很難找到最優策略，這也是為什么一開始 Edmonds 的算法沒有得到廣泛應用。

7 Y3 K1 J, n3 \& T" F5 y6 X, g

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

       而從2001年開始，北美的一些大城市就開始用比較成熟的軟件（如 ArcGIS）來規劃鏟雪車的行車路徑。這些軟件一般會把一大塊城市交通網分割成一小塊一小塊的，然后分別再進行計算。

5 i" O$ m, G4 g/ j) q: r

        比如，多倫多在用圖論原理對鏟雪線路進行規劃后，鏟雪費用比之前減少了三分之一，每年節省了大約3百萬美金（約合2千萬人民幣）。

8 N: D$ U& x$ x4 I

       多倫多的市政道路交通的運營經理 Hector Moreno 表示，在用ArcGIS之前，行車路線主要靠經驗和人工計算，現在就不需要這么麻煩了。

4 g8 U6 ]0 t* f7 s  T, N" p# e

波士頓市政府的應用數學團隊 圖片來源：boston.gov

       2010年，波士頓市政府也組建了自己的數學團隊——Mayor's Office of New Urban Mechanics，用數學和計算機來規劃鏟雪路線。

       像波士頓這樣的大城市用數學進行規劃真的太有必要了。2015年，為了鏟雪，波士頓的鏟雪車一共開了47萬千米，差不多可以繞地球12圈了。鏟雪的花費也是驚人的，那年的暴雪讓波士頓一共掏出了3500萬美金（約合2.3億人民幣）。

( f: b* U0 W6 P" ~  {6 a! R  W

2015年，波士頓的暴雪創下了記錄。圖片來源：newyorktimes

- O6 n4 k, U, m) b0 p

       除了道路養護，中國郵差問題的算法在很多領域還有應用。比如在交互設計時，中國郵差問題就被用于終端產品的可用性檢測。

舉個例子，一個手機被制造出來以后，手機制造商想要看看每個功能是不是和名稱相符。比如按下主鍵，點開“設置”，再點開“網絡”，是不是真的會出現網絡設定功能。

" W3 a. j) q1 {& U

       因為手機的功能很復雜，不同功能之間形成的網絡要怎么樣才能有效地走個遍，這個問題有時連制造商也搞不太明白。1996年諾基亞出的2110的菜單有88個項目，一共有273種操作。如果隨便按，可能一些菜單永遠也不會得到檢測。

* b& q7 i( X+ B

      但是利用中國郵差問題的算法就能規劃測試路徑和計算步驟數量了：最少就只需要按594次鍵盤按鈕就可以把所有的菜單和功能都過一遍了。

  |' H9 A# h  _( x- x, j  E& w5 w

      在檢查網頁鏈接有沒有“死角”的時候也可以用到中國郵差問題的算法。

% S' r$ L: |3 Y" l+ T( ?

      比如，富蘭克林故居的網站(benjaminfranklinhouse.org)有66個網頁，1191個超鏈接。如果網絡測試員沒有頭腦一頓亂點，不但要做無用功，有些網頁和鏈接可能還點不到。但是利用中國郵差問題的算法，測試員知道只要點2248次就可以測試完所有的網頁和超鏈接了。

位于英國倫敦的富蘭克林故居

) {3 u! S+ `" a/ y" |) B/ G

       歐拉路徑判定挺好掌握的呢：口中串串，乃米田共。

- \( Q6 B) s) B0 E0 l6 u

- q/ c) L4 y1 E. u! T/ u7 C

大白小白

口中串串，乃米田共？？

okmeiyou

學習了。

譬如朝露

最后一句，是本文之主旨所在

曉昀

譬如朝露 發表于 2020-9-6 18:36
2 y1 I0 C9 Q' P% [) {& \最后一句，是本文之主旨所在

" k; e+ H/ X! X' v( i- B超快速抓住重點。這是很有意思的一個問題。
- c( B/ v! `# a. Z4 G+ d5 i+ T1 y

kayex

不能這樣的，一定要按領導規定的路線開才對，領導高興最重要?。。?/td>

魍者歸來

七橋這個是奧數的典型問題之一，噩夢復現。
8 S$ U! n2 l, g/ B8 m5 E3 J9 {* v
* P0 V7 M- ^; \2 ?說個題外話，以前還經常有公車私用，拉警笛闖紅燈的，現在不少城市都開始聯網了，不是出任務的情況拉警笛會被處罰，確實規范了不少。

遠祥

抓重點，提關鍵，也可以使用思維導圖。

wlj0202

學習一下啊了