DEEPgeneratedpublished

从巴基斯坦上一艘船,方向盘焊死一米都不转,能笔直开到哪

分支定界算法(Branch and Bound)机制

从巴基斯坦上一艘船,方向盘焊死一米都不转,能笔直开到哪? 堪察加半岛,俄罗斯远东。 整整 32089 公里。 绕过大半个地球,相当于赤道周长的百分之八十。 途中穿过印度洋、避开马达加斯加、擦过南极与南美洲之间的德雷克海峡、横跨整个太平洋,不碰任何一块陆地。 在平面的二维地图上看,这是一条扭曲怪异的巨大波浪线。 但在真实的三维球体上,它是绝对的直线。 同样的事情也发生在陆地上。 从中国福建晋江出发,不打一把方向盘,可以一路笔直开到葡萄牙的萨格里什。 全长 11241 公里,横穿欧亚大陆 15 个国家,中间连一个大型水体都撞不到。 这事最早在 2012 年由 Reddit 网友提出,在网上吵了整整六年。 所有人都在争:地球海岸线是分形的,岛屿星罗棋布,你怎么证明中途没有蹭到某个无名礁石? 为什么没人早点用计算机把它算出来? 因为算不动。 如果用 1 角分精度的全球高程模型把地球切开,要在球面上穷举所有可能的大圆航线,一共有 2.33 亿条。 要验证这些路径上的每一个坐标点,需要排查超过 5 万亿次。 把最顶级的超级计算机搬来做暴力穷举,也得耗费数年。 2018 年,两位物理学家 Rohan Chabukswar 和 Kushal Mukherjee 写了一篇论文,把这个看似无解的死局破了。 他们没有找超算,只用了一台普通的笔记本电脑。 只花了 10 分钟。 他们没靠硬件蛮力,用的是运筹学里的经典武器:分支定界算法(Branch and Bound)。 这套算法的逻辑极度精巧。 它根本不去挨个检查那 2.33 亿条航线。 它把成千上万条路径打包成一个集合,先计算这个集合在理论上能达到的最大无障碍长度。 如果一个集合能给出的最好上限,还不如手里已经找到的一条已知航线长,整个分支就会被瞬间砍掉。 一个坐标点都不用再算。 通过一层层递归与数学定界,绝大多数无效计算被成片剪除。 一个原本需要数百年的天文数字,被压缩成了几分钟的代码运行。 很多人以为解决极限难题靠的是堆砌算力。 算力只是蛮力。 在面对指数级爆炸的复杂现实时,真正的突破,在于先在数学上证明哪些地方根本不用看。 剪枝比算力更昂贵。 知道什么可以忽略,比把所有东西都算一遍,要聪明得多。

引用 / CITATIONS

No citations exported.

导出 / EXPORT

订阅 · SUBSCRIBE

新的深度解读发布时,会在每周简报里送到你邮箱。

不追踪邮件打开与邮件链接点击,一键退订。 或用 RSS · 详情