數學家破解「8萬間酒吧巡禮」最佳路徑！算完要178天

「這會是一場超長的酒吧巡迴之旅。」加拿大滑鐵盧大學組合數學與最佳化教授威廉·庫克如此輕描淡寫地描述。這位參與破解難題的數學家計算出：「完成整趟旅程總共需要15,386,177秒，也就是178天1小時56分17秒。」他還幽默補充：「途中你可能需要停下來喝很多杯。」

雖然這個結果既有趣又實用，但研究初衷可不是要幫韓國酒鬼規劃長達半年的暢飲路線。這其實是在演示一個源自兩世紀前的經典數學難題——「旅行推銷員問題」：如何用最短路線走遍地圖上所有地點並返回起點？

舉個簡單例子：假設你住在紐約，要造訪周邊三座城市再回家，最短路線該怎麼走？直覺選擇的路程是2,285公里，但其實存在更優解——2,277公里，省下8公里。聽起來很簡單？

但就像許多數學問題，旅行推銷員問題「說起來容易算起來要命」。它屬於「NP困難」問題，意味著求解所需時間會隨問題複雜度呈指數級暴增。庫克教授解釋：「以南韓81,998間酒吧為例，可能的路線組合數量約是2後面跟著367,308個零。即使每秒能檢查百萬種路線，所需時間仍遠超宇宙年齡。」

研究團隊運用兩大關鍵技術突破困境：目前最優的「林-克尼根啟發式算法」，以及能分叉驗證的「切割平面法」。最終他們成功計算出穿越33.6億個點對點行程的最佳路線，不僅展現數學實力，更驗證了方法的強大效能。

唯一可惜的是，當你用最有效率的方式喝完8.2萬間酒吧後，大概也沒人能清醒理解這項成就了。乾杯！