计算出地球上最长的直线海洋路径
一对研究人员,一个在联合技术研究中心,另一个在 IBM 研究中心,开发了一种算法,可用于确定地球上最长的直线路径。在上传到arXiv预印本服务器的论文中,Rohan Chabukswar 和 Kushal Mukherjee 描述了他们的算法及其揭示的内容。
这两位研究人员创建了他们的算法,以回应 Reddit 上一位不知名人士(他被确认为帕特里克·安德森)的帖子——他发布了他声称是地球上最长的直线海洋旅行。与该帖子一起的图片显示了提议的直达路线,但没有证据表明它是如何被发现的。对这个命题很感兴趣,两位研究人员想知道他们实际上如何计算这样一条线。他们知道可以使用蛮力方法来做到这一点,这将涉及测量每一段海洋的长度。但是,他们指出,这可能需要比他们拥有的更多的计算机能力。从 NOAA 获得的全球地图提供了 1.8 公里的分辨率,他们发现,使用蛮力方法需要研究描述超过 2300 亿个大圆的数据。这意味着要分析数万亿个单独的数据点——对于他们可用的计算机来说显然太多了。为了减少工作量,他们求助于数学——特别是称为分支定界的优化算法。此类算法通过将路线分配给本身包含相似路线子集的分支来减少搜索量。随着算法的运行,子集被分析并消除分支,筛选需要分析的数据量,直到找到包含解决方案的分支。称为分支定界的优化算法。此类算法通过将路线分配给本身包含相似路线子集的分支来减少搜索量。随着算法的运行,子集被分析并消除分支,筛选需要分析的数据量,直到找到包含解决方案的分支。称为分支定界的优化算法。此类算法通过将路线分配给本身包含相似路线子集的分支来减少搜索量。随着算法的运行,子集被分析并消除分支,筛选需要分析的数据量,直到找到包含解决方案的分支。
通过编码和运行他们的算法并输入地图数据,研究人员发现他们的笔记本电脑只需要十分钟就可以提供答案。有趣的是,安德森给出的答案是一样的,据报道他是从一个未知的 Wiki 帖子中获取信息的。这条线从巴基斯坦海岸线上的一个点一直延伸到俄罗斯海岸线,距离约为 32,089.7 公里。