七君

【適用話題】最佳路線 數(shù)學(xué)之美科學(xué)與生活 學(xué)以致用

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

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

掃馬路車、灑水車、鏟雪車這類問(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.Goldman把這個(gè)問(wèn)題命名為“中國(guó)郵差問(wèn)題”。

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

而從2001年開(kāi)始，北美的一些大城市就開(kāi)始用比較成熟的軟件，如ArcGIS來(lái)規(guī)劃鏟雪車的行車路徑。這些軟件一般會(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è)例子，一部手機(jī)被制造出來(lái)以后，手機(jī)制造商想要看看每個(gè)功能是不是和名稱相符。比如，按下主鍵，點(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次鍵盤按鈕，就可以把所有的菜單和功能都過(guò)一遍。

（張秋偉摘自微信公眾號(hào)“把科學(xué)帶回家”）

【素材分析】數(shù)學(xué)不只在星空之上，也在社會(huì)生活之中。比如“中國(guó)郵差問(wèn)題”其核心就是解決路徑浪費(fèi)，以最短的時(shí)間，最少的路程來(lái)完成一片區(qū)域的覆蓋。近年來(lái)，從人工智能、大數(shù)據(jù)到航空航天、國(guó)防安全，從生物醫(yī)藥、能源、海洋到金融、機(jī)械制造，諸多領(lǐng)域的重大科技突破都是以數(shù)學(xué)科學(xué)的發(fā)展和進(jìn)步為基礎(chǔ)的。學(xué)好數(shù)學(xué)不僅僅是為了考好的成績(jī)，更是培養(yǎng)優(yōu)秀的數(shù)學(xué)思維能力，應(yīng)用在生活工作的方方面面。

【速用名言】

1.宇宙之大，粒子之微，火箭之速，化工之巧，地球之變，生物之謎，日用之繁，無(wú)處不用數(shù)學(xué)。——中國(guó)數(shù)學(xué)家 華羅庚

2.不管數(shù)學(xué)的任一分支是多么抽象，總有一天會(huì)應(yīng)用在這實(shí)際世界上?！砹_斯數(shù)學(xué)家 羅巴切夫斯基

（特約教師 王文炎）