張貼日期：Aug 23, 2016 8:16:47 AM
作者：賴以威 副教授（國立臺灣師範大學電機工程學系、數感實驗室）
作者：陳宏賓 副教授（國立中興大學應用數學系）
2016年你不可不知的手機遊戲，絕對是任天堂投資的 The Pokémon Company 開發的Pokémon Go 這款巨作。蝦密！你居然不知道什麼是 Pokémon？趕快偷點一下看維基百科。根據知名手機應用程式市場研究機構 Sensor Tower 的統計資料顯示，自從Pokémon Go 在今年 7 月 6 日於澳洲及紐西蘭公開下載，截至目前已經在全球超過 55 個國家發行，全球總下載量突破 1 億次。這股熱潮有多瘋狂呢？從 Pokémon Go 下載次數達到 5000 萬只花了 19 天就能夠看得出來，比起之前的熱門手遊 Candy Crush 用了 112 天來說，神奇寶貝創下的這個紀錄真的是非常神奇阿!
Credited by Sensor Tower
專注於使用數學觀點來解讀時事的優質媒體《數感實驗室 Numeracy Lab》，這次運用麥當勞賣出漢堡的速度來做對比，讓民眾可以更容易感受神奇寶貝被下載的速度有多快。
神奇寶貝既然這麼紅，想必大家都已經知道要怎麼玩了，我就不再多說。這款遊戲最特別的地方乃在於結合了擴增實境（Augmented Reality，簡稱AR）技術，整個遊戲是建立在現實世界之上。因此，玩家必須在現實世界的地圖中東奔西跑去抓寶貝，這可能是遊戲的最大賣點之一。不過這個特性卻也造成玩家一個很嚴重的問題－腳軟。如何走最短的路徑Catch ‘em all 成了最大挑戰！
挑戰：要怎麼走最少的路抓到城市中所有神奇寶貝？
旅行業務員問題（Traveling Salesman Problem）
神奇寶貝所引起的數學難題，其實是一個非常經典的數學問題，數學家很早就開始關注了。故事從 1962 年說起。
1962 年，P&G 公開懸賞了一則問題：
「以芝加哥為起點和終點，該如何開車，才能在最短路徑內環遊 33 個特定的景點？」
這問題看起來沒什麼大不了，但 P&G 在後面補了一句話
「.....能解出最短路徑的人，將獲得一萬美金的獎金。」
當時的一萬美金可是足以買下一棟房子。
P&G 會出這麼高的金額，表示這個問題
1. 有對應的巨大實用價值。對物流來說，能夠以最短路徑完成送貨，即可降低汽車、人力時間成本。
2. 一定非常難。一般人直覺的作法可能是列出所有的路徑，再從其中挑選最好的，這樣子挑選出來的解答肯定是最好的，乍看之下不失為一個好主意。
然而，要窮舉出所有的路徑，就算是阿湯哥來也是不可能的任務！
假設有 26 個城市，從任一城市出發走過其他 25 個城市的走法，共有 25x24x…x1 = 25! 條不同的路徑，數學寫起來頗輕鬆寫意，但 25! 大約近似於 1.55x1025 ，實際上是一個超級天文數字。用電腦跑的話可能在太陽變成白矮星之前也跑不完。
圖為白矮星，由NASA, ESA, H. Bond (STScI), and M. Barstow (University of Leicester) - http://www.spacetelescope.org/images/html/heic0516a.html，CC BY 3.0，https://commons.wikimedia.org/w/index.php?curid=477445
稍作估計就可以得到這個簡單的結論：假設電腦每秒可以處理 1000萬 = 107 條路徑的計算，乘以一年有 3.15x107 秒，知道一年可以處理 3.15x1014 條路徑計算，因此 1.55x1025 大約還需要….
500億年！
而根據天文學家估計，太陽的壽命只有70億年。（目前認為白矮星是中低質量恆星演化的最終產物，太陽屬於其中之一。）
話又說回來，P&G 顯然對數學界不太熟悉。因為早在 1954 年(距離 P&G 提出問題的 8 年前)，就有一組數學家解決了更巨大的「49 座城市」的旅行問題。
這群數學家包括了人稱線性規劃之父的 George Dantzig，20 世紀最偉大的應用數學家之一。Dantzig 的解決方案非常精緻也是數學證明中最常見的手法。
George Dantzig (From Wikipedia)
他先「證明」走遍給定的 49 座城市一定需要 12,345 英里以上。再提出一條路線，恰恰好只需要 12,345 英里。他所發明的演算法，也成了後來旅行業務員演算法的基礎。然而不知道為什麼，Dantzig 沒去「領」P&G 懸賞的一萬元獎金。也因為他沒去，導致 P&G最後出現有點尷尬的狀況：他們收到很多結果，但不知道答案是什麼....
P&G 最後從所有答案中挑出最短的那條路徑作為答案。請注意，這不一定是「所有可能中的最短路徑」。事實上，最後得獎的是來自 Carnegie Mellon University 的 Gerald Thompson。不過，他也坦承自己無法證明這是最短路徑。
有趣的是，跟他交出一樣答案的還有好幾個人， P&G 只好要求這些人來比一場關於 P&G 產品的散文競賽，最後 Thompson 脫穎而出。這故事告訴我們，果然文理雙修是必要的啊。
再回到旅行業務員問題，這個問題在之後的幾十年，陸續有各種更省時的演算法被開發，陸續在各種領域找到應用。最終成了一個經典的數學最佳化問題。
數學模型
將神奇寶貝所在的地點視為一個頂點 (Vertex)，把兩兩頂點用一條邊 (Edge) 連接起來，並且在邊上賦予一個權重 (Weight) 代表這兩點的距離，則 V（收集所有頂點）、E（所有的邊）和 W（其權重函數）所形成的圖 G＝（V,E,W）就是一個用數學語言抽象化之後的模型。這種使用頂點和邊描述問題的學問屬於圖論的研究範疇。數學家要追求的是
能不能找到一個有效率的方法走遍所有的頂點，並且對於任意給的圖 G 都能適用？
不幸的是，旅行業務員問題非常困難，目前並沒有一套有效率的好方法，用演算法的角度來說，它屬於 NP-hard 的問題，可以理解成目前仍不知道有沒有多項式時間可解的方法。如果你有，那你就準備揚名全世界，並且獲得克雷數學研究所頒發 100 萬美元的獎金。
有些讀者可能感到奇怪，前面不是說有一群優秀數學家已經給出一個 49 座城市的旅行問題的最短路徑解法，這不是前後矛盾？事實上，針對特定的例子，尤其是小規模的，比如說 49 座城市，我們總是可以利用一些額外的資訊和幾何原理，縮小搜尋最佳解的範圍，使其變成一個用目前的電腦可以處理的特例。
這次的神奇寶貝也不例外。加拿大滑鐵盧大學數學系有一群數學家，已經用數學的方法計算出美加地區的幾個大城市抓神奇寶貝的最短路徑(http://www.math.uwaterloo.ca/tsp/poke/index.html)。
圖為波士頓地區最佳路徑圖(From http://www.math.uwaterloo.ca/tsp/poke/index.html)
以紐約市來說，68 個點一共需要走 215 公里，但如果放棄甘迺迪機場，只鎖定曼哈頓島，倒是可以根據演算法規劃出來的路線，好好來一場與神奇寶貝邂逅的午後漫步。
相似卻大不相同的中國郵差問題
數學上經常與旅行業務員問題拿出來相提並論的，稱為中國郵差問題（Chinese Postman Problem），目前只有極少數數學問題冠名中國，這是其中之一，為了紀念第一個提出這個問題的中國數學家管梅谷。同樣地，考慮任意一個圖 G=(V,E,W)，中國郵差問題想問的是
有沒有一個有效率的好方法走過所有的「邊」？
一個是走過所有的「頂點」，一個是走過所有的「邊」，看起來極相似的兩個問題命運卻大不同！相對於旅行業務員問題是 NP 問題，中國郵差問題則是 P 問題，也就是說可以在多項式時間內找到最佳解。註：有向圖中的中國郵差問題仍是屬於 NP 問題。
雖然有點不可能，但倘若神奇寶貝是早了一個世紀被發現，那「旅遊業務員問題」很可能就會從此改名為「神奇寶貝問題 (Pokémon Problem)」，然後在各個領域，電機、通信、資工、交通，都可以看到神奇寶貝問題的蹤影。
最後，要是哪天台北市的驛站標定清楚，或許數感實驗室也能來幫忙，規劃出各區的「神奇寶貝散步路線」噢。
延伸閱讀