Pokémon Go 指南: 如何用數學幫助你 Catch ’em all
posted 22 hours ago by 陳宏賓
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 (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 座城市，我們總是可以利用一些額外的資訊和幾何原理，縮小搜尋最佳解的範圍，使其變成一個用目前的電腦可以處理的特例。
以紐約市來說，68 個點一共需要走 215 公里，但如果放棄甘迺迪機場，只鎖定曼哈頓島，倒是可以根據演算法規劃出來的路線，好好來一場與神奇寶貝邂逅的午後漫步。
相似卻大不相同的中國郵差問題
數學上經常與旅行業務員問題拿出來相提並論的，稱為中國郵差問題（Chinese Postman Problem），目前只有極少數數學問題冠名中國，這是其中之一，為了紀念第一個提出這個問題的中國數學家管梅谷。同樣地，考慮任意一個圖 G=(V,E,W)，中國郵差問題想問的是
有沒有一個有效率的好方法走過所有的「邊」？
一個是走過所有的「頂點」，一個是走過所有的「邊」，看起來極相似的兩個問題命運卻大不同！相對於旅行業務員問題是 NP 問題，中國郵差問題則是 P 問題，也就是說可以在多項式時間內找到最佳解。註：有向圖中的中國郵差問題仍是屬於 NP 問題。
雖然有點不可能，但倘若神奇寶貝是早了一個世紀被發現，那「旅遊業務員問題」很可能就會從此改名為「神奇寶貝問題 (Pokémon Problem)」，然後在各個領域，電機、通信、資工、交通，都可以看到神奇寶貝問題的蹤影。
最後，要是哪天台北市的驛站標定清楚，或許數感實驗室也能來幫忙，規劃出各區的「神奇寶貝散步路線」噢。
延伸閱讀 捷運地下委員會的旅行業務員問題 ，賴以威，泛科學 PanSci。波士頓大雪底下埋藏了中國郵差 － 暴風雪中的數學，陳宏賓，UniMath。
作者簡介
賴以威－數學作家、譯者。
作品散見於聯合報、未來少年、國語日報，與各家網路媒體。師大附中，台大電機畢業。 我深信數學大師約翰·馮·諾伊曼的名言「If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is」。為了讓各位跟我一樣相信這句話，我們得先從數學有多簡單來說起，聊聊數學，也用數學說故事。 歡迎加入我與太太廖珮妤一起創辦的： 數感實驗室 。 陳宏賓 － UniMath 主編、逢甲大學應用數學系助理教授。 數學既深且廣，我懂得不多，最喜愛組合數學相關領域，主要研究興趣是群試理論、圖論及最優化分解。2013 年出版「Partitions: Optimality and Clustering, Volume II: Multi-Parameter」一書（與 Uriel Rothblum 和 Frank K. Hwang 教授合著）。對於數學和教育有強烈的熱忱和使命感，積極創立 UniMath 電子數學媒體，致力於推廣數學文化。 |
沒有留言:
張貼留言