七君

大家有沒(méi)有想過(guò)，平時(shí)路上的灑水車(chē)、鏟雪車(chē)是怎么規(guī)劃行車(chē)路線的呢？

有人會(huì)說(shuō)，這還不簡(jiǎn)單，哪兒沒(méi)有跑過(guò)就去跑一遍不就行了。這種方法的確能保證所有的道路都被打掃了，但是車(chē)子可能會(huì)在某幾段馬路上重復(fù)開(kāi)，損失燃油和時(shí)間。

掃馬路車(chē)、灑水車(chē)、鏟雪車(chē)這類(lèi)問(wèn)題在數(shù)學(xué)上屬于“中國(guó)郵差問(wèn)題”，早在20世紀(jì)70年代就有了靠譜的解法。

這還要從1962年說(shuō)起。當(dāng)時(shí)，毛主席鼓勵(lì)科學(xué)家們用科學(xué)解決日常生活中遇到的問(wèn)題。我國(guó)數(shù)學(xué)家管梅谷就想到了這樣一個(gè)問(wèn)題：一個(gè)郵差走遍每條街道去送信，最短路徑應(yīng)該是什么樣的？后來(lái)，美國(guó)數(shù)學(xué)家AlanJ. Go l dman把這個(gè)問(wèn)題命名為“中國(guó)郵差問(wèn)題”。

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

其實(shí)，歐拉在1735年就研究過(guò)一個(gè)和管梅谷類(lèi)似的問(wèn)題——七橋問(wèn)題，并得到了一些重要的結(jié)論。

七橋問(wèn)題和我們小時(shí)候玩的一筆畫(huà)的益智問(wèn)題類(lèi)似：在普魯士的柯尼斯堡有兩個(gè)小島，兩個(gè)小島和附近一共有7座橋連通?，F(xiàn)在問(wèn)題來(lái)了，怎樣規(guī)劃路線才能恰好經(jīng)過(guò)每一座橋一次？

第二年，歐拉發(fā)表了一篇論文，證明七橋問(wèn)題不可解，原因是他給出了能解的一般條件，那就是每塊地都必須有偶數(shù)座橋，而七橋問(wèn)題不符合這種情況。這類(lèi)問(wèn)題在數(shù)學(xué)上發(fā)展成了圖論和拓?fù)鋵W(xué)。而因?yàn)闅W拉的開(kāi)創(chuàng)性貢獻(xiàn)，能夠一筆畫(huà)的圖被叫作歐拉圖，能一筆畫(huà)的路徑被叫作歐拉路徑。

七橋問(wèn)題等價(jià)于下面這個(gè)圖形。歐拉證明，只有當(dāng)奇頂點(diǎn)的數(shù)量等于0或2時(shí)，才存在一筆畫(huà)。七橋問(wèn)題的奇頂點(diǎn)（藍(lán)點(diǎn)）的數(shù)量等于4，因此無(wú)法一筆畫(huà)。

歐拉還證明了一張圖能一筆畫(huà)的一般情況：奇頂點(diǎn)（也就是邊的數(shù)量是奇數(shù)的頂點(diǎn)）的數(shù)量等于0或2。所以按照歐拉證明的定理，中文的“串”就可以一筆寫(xiě)成，因?yàn)樗钠骓旤c(diǎn)只有最上面和最下面兩個(gè)。

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

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

隨著計(jì)算機(jī)技術(shù)的進(jìn)步，一些數(shù)學(xué)家開(kāi)始嘗試把中國(guó)郵差問(wèn)題應(yīng)用到日常生活中。比如，明尼蘇達(dá)大學(xué)的數(shù)學(xué)教授Peh Ng就曾用圖論的思想幫明州莫里斯市政府規(guī)劃冬季的鏟雪線路。

而從2001年開(kāi)始，北美的一些大城市就開(kāi)始用比較成熟的軟件，如ArcGIS來(lái)規(guī)劃鏟雪車(chē)的行車(chē)路徑。這些軟件一般會(huì)把一大塊城市交通網(wǎng)分割成一小塊一小塊的，然后分別再進(jìn)行計(jì)算。比如，多倫多在用圖論原理對(duì)鏟雪線路進(jìn)行規(guī)劃后，鏟雪費(fèi)用比之前減少了三分之一，每年節(jié)省了大約300萬(wàn)美元（約合人民幣2000萬(wàn)元）。

除了道路養(yǎng)護(hù)，中國(guó)郵差問(wèn)題的算法在很多領(lǐng)域還有應(yīng)用。比如，在交互設(shè)計(jì)時(shí)，中國(guó)郵差問(wèn)題就被用于終端產(chǎn)品的可用性檢測(cè)。舉個(gè)例子，一個(gè)手機(jī)被制造出來(lái)以后，手機(jī)制造商想要看看每個(gè)功能是不是和名稱(chēng)相符。比如，按下主鍵，點(diǎn)開(kāi)“設(shè)置”，再點(diǎn)開(kāi)“網(wǎng)絡(luò)”，是不是真的會(huì)出現(xiàn)網(wǎng)絡(luò)設(shè)定功能。

因?yàn)槭謾C(jī)的功能很復(fù)雜，不同功能之間形成的網(wǎng)絡(luò)要怎樣才能有效地走個(gè)遍，這個(gè)問(wèn)題有時(shí)連制造商也搞不太明白。1996年諾基亞出的2110的菜單有88個(gè)項(xiàng)目，一共有273種操作。如果隨便按，可能一些菜單永遠(yuǎn)也不會(huì)得到檢測(cè)。但是利用中國(guó)郵差問(wèn)題的算法就能規(guī)劃測(cè)試路徑和計(jì)算步驟數(shù)量了：最少只需要按594次鍵盤(pán)按鈕，就可以把所有的菜單和功能都過(guò)一遍。

//摘自把科學(xué)帶回家微信公眾號(hào)，本刊有刪節(jié)/