計算機科學家發(fā)現(xiàn)一條可以無阻礙環(huán)游世界的航路

一場始于Reddit的爭論終于得到了解決。這一問題是如何在不撞擊陸地阻礙物的情況下以直線行駛環(huán)游世界?？匆幌逻@里的圖像，很明顯這些路徑不是一條直線。但是請注意，地球球面上的直線表示在平面地圖上為一段圓弧。

來自愛爾蘭聯(lián)合技術(shù)研究中心的Rohan Chabukswar和來自印度IBM Research的Kushal Mukherjee了一種算法，可以計算出海上或陸地上最長的直線路徑。這對搭檔展示了他們的作品。

該算法使用一種稱為分支和綁定的技術(shù)。這是通過觀察所有可能的解決方案，如樹的分支。算法然后檢查一個又一個分支。通過界定邊界來減少確定分支需要的工作量。它本質(zhì)上是在一系列分支中尋找可能的解，并試圖找到一個更接近最優(yōu)值的子集。

如果分支不接近最優(yōu)解，則完全忽略它。這兩位研究人員說，他們的算法在大約10分鐘內(nèi)算出了最長的水路徑。陸地最長的直線距離需要45分鐘才能找到。這兩種路徑都是在一般的筆記本電腦上運行的。

有趣的是，這條“水之路”其實和Reddit用戶kepleronly所知道的幾乎一樣，他在2012年也發(fā)現(xiàn)了類似的最長路徑。研究人員繪制的路徑長32089.7公里，途經(jīng)15個國家，跨度為11,241.1公里。