计算机科学家发现一条可以无阻碍环游世界的航路
一场始于Reddit的争论终于得到了解决。这一问题是如何在不撞击陆地阻碍物的情况下以直线行驶环游世界。看一下这里的图像,很明显这些路径不是一条直线。但是请注意,地球球面上的直线表示在平面地图上为一段圆弧。来自爱尔兰联合技术研究中心的Rohan Chabukswar和来自印度IBM Research的Kushal Mukherjee了一种算法,可以计算出海上或陆地上最长的直线路径。这对搭档展示了他们的作品。该算法使用一种称为分支和绑定的技术。这是通过观察所有可能的解决方案,如树的分支。算法然后检查一个又一个分支。通过界定边界来减少确定分支需要的工作量。它本质上是在一系列分支中寻找可能的解,并试图找到一个更接近最优值的子集。如果分支不接近最优解,则完全忽略它。这两位研究人员说,他们的算法在大约10分钟内算出了最长的