張貼日期：Mar 02, 2015 4:48:39 PM
作者：陳宏賓 副教授（國立中興大學應用數學系）
數學，有用嗎? 來看看怎麼利用數學對抗暴風雪...
路透社報導，今年 2 月初大型風暴猛烈襲擊美國東北部，波士頓地區降下的大雪量，創下波士頓史上單週降雪量之最，波士頓地區覆蓋了一層厚厚的白雪，陸上交通大受影響。為了盡快恢復整個城市的運作，政府派出了大量的剷雪車和灑鹽車。截至目前為止，已經耗費 185,000 卡車司機工作時數，總里程達 293,000英里，足足可以繞地球 12 圈，並且用了 76,000 公噸的鹽。為了剷除這場大雪，已經耗費了 35,000,000 美金，這個數字，還在持續增加中。
為求盡快恢復，除了再投入更多的剷雪車和灑鹽車之外，如何讓這些卡車工作得更有效率是當下最重要的議題。而重點在於，分配工作路線時不要讓卡車原路往返，因為原路往返表示浪費了一趟。
你有好方法嗎? 沒關係! 數學家有。
西元 1735 年春天，右眼因為長時間專注於研究工作而導致失明的瑞士數學家歐拉 (Leonhard Euler)，在太太的要求下，暫時放下了手邊工作，全家一起到風光明媚的柯尼斯堡 (Königsburg) 度假，現今大約位於俄國境內 Kaliningrad 附近。這座城市跨越了普列戈利亞河的兩岸，河的中央有兩個小島，小島和河的兩岸共有七座橋相連接(如圖)。當地流傳了一則謎題:
要如何才能從某一塊土地開始，將每座橋恰好經過一次，然後回到原地?
還有傳說走完柯尼斯堡的七座橋恰好一次或拔到獅子的鬃毛，都能夠讓掉落的頭髮長回來...(誤)
漫步在橋上的歐拉，一聽到這個謎題，完全把太太所謂度假休養的要求拋在腦後，邊走腦袋邊飛快的運轉了起來。不過，他想的並不只是回答七橋問題不可能辦到而已，擁有過人洞察力的歐拉渴望給出一般的規則，能夠適用於各種情況。隔年，歐拉發表了一篇文章，不僅解決了七橋問題，同時給出了一個更一般的結論:
如果找得到這種路線，那麼每塊土地都必須有偶數(0,2,4,6,...)座橋連接；反之亦然。
這種路徑後來被稱為「歐拉迴路」。而這也就是俗稱的一筆劃問題。
1736 年歐拉的這篇文章奠下了數學中圖論這門學問的基礎。歐拉將這種學問視為一種特殊的幾何問題，並且提到是萊布尼茲 (Leibniz) 最早開始考慮這類幾何，稱為「位置的幾何學 (geometria situs)」。後來，這種不考慮距離只關注構造的幾何，朝著兩條不同的路線發展，一條成了圖論 graph theory，一條變成了拓樸學 topology。兩者的不同處在於，圖論少了複雜的幾何結構，只保留了點跟邊兩種最單純的元素，由於圖論的闡述經常帶有濃厚的離散意味，因此，被歸類在離散數學的一支。
太棒了，剷雪問題就此解決囉，對吧?! 等等，慢著!!!
歐拉的條件換到這個地方，是指每個路口都得有偶數條路連接。
整個城市都是我的咖啡館十字路口當然沒問題，萬一遇到 T 字路口呢? 歐拉的結論正意謂著在現實生活中，某些路走兩次以上幾乎是無可避免的事啊!
Chinese Postman Problem 中國郵差問題
自歐拉 1736 年發表了圖論的第一篇論文，之後的兩三百年間，圖論的研究開始百家爭鳴蓬勃發展，好不熱鬧。然而，卻一直到了西元 1962 年左右，中國數學家管梅谷才開始考慮這個問題:
一個郵差要送信到每條路的每個房子，最短路徑該怎麼走?
把路口看成點，道路當成邊，換成圖論的語言，即是:
在一個圖上，如何找一條最短路徑通過所有的邊?
當然，一般來講，路口可以有奇數或偶數條路連接。他將這個問題稱為「Postman Problem (郵差問題)」 (後來才被稱為「Chinese Postman Problem 中國郵差問題」)，並且提出了一個解答，不過沒那麼理想。1973 年美國數學家 Edmonds 提出了一個更有效率的演算法。簡單來說，他的方法就是先去找所有具有奇數度的點(連接奇數條邊的那些點)，根據歐拉的說法這些點正是無法避免原路往返的點，找出他們兩兩之間的最短路徑，剩下的都是偶數度的點所以存在歐拉迴路，將這些路徑和迴路組合在一起，就是一個最佳解。在數學世界裡。
現實世界
明尼蘇達大學的數學教授 Peh Ng 驕傲的說: "Even if you give me a layout of 220,000 lines and 300,000 intersections, it’s really doable.” 事實上，在 1990 年代，她就曾用演算法去幫助解決家鄉 Morris 的剷雪問題。
不過，可以想見，實際上遭遇的狀況，遠比中國郵差問題的設定還要複雜許多。首先，剷雪卡車不會只有一輛，可能有幾十輛。高速公路或重要道路要能夠優先通行。卡車司機工作時數不能超時，還要盡量讓每個司機工作時數相同...等等。這時候如何分配每輛卡車處理的區域，讓整體的效益最好，屬於最優化 (optimization) 領域的研究範疇。以我的研究經驗來看的話，會將它視為一個最優化分解 (optimal partitions) 的多變數和分解問題 (sum partition problems)。由於眾多參數的引進，在大部分時候，找到最佳解是一件非常困難的任務。
不過，還好現實生活中，我們只需要一個不錯的解答就可以了。
現在，一旦遭遇大雪襲擊，一些大型的城市，像多倫多，就使用現成的商業軟體(如ArcGIS 阿基師)來輔助規畫。只要輸入各項參數，它就會自動跑出優化過的剷雪路徑。自 2001 年開始使用這類輔助系統，多倫多市在冬季時剷雪及道路灑鹽保養的耗費已經獲得了可觀的改善。根據統計，多倫多現在一年只要花 8,000,000 美金，比起 2001 年以前的花費，節省了 30%，約 3百萬美金 = 參加一次海珊的慈善賭王撲克大賽 = 1萬個小學生1年的營養午餐。
你說，數學有用嗎?