北京
画一张大地图得花10小时，换成一条曲线，时间直接砍到半小时。这个反差来自数学里一个奇特的概念——空间填充曲线，它把低维的线段连续映射到高维的面上，走到哪儿就覆盖到哪儿。
这种曲线的妙处在于：一旦进入一个区域，它就会逐个扫过区域内所有点。于是平面上挨得近的点，在曲线上也挨着出现。L. Platzman 和发明者就利用这一性质，搞出了一个旅行商问题的启发式算法：把要去的位置，按空间填充曲线经过的顺序串起来，就得到一条不算绕远的路。对随机分布的点，这条路预期只比理论最优解长约 25%。
如果只看那个 25%，可能觉得划不来。但换个角度看，传统算法得把点之间的精确距离算个遍，而这个启发式完全跳过这步，不需要测距。它的算法代价也低：跑 n 个点只需 O(n log n) 的工夫，增减一个点也只要 O(log n) 刷新一下。更关键的是它能天然并行化，而常用的最近邻算法压根做不到这一点。
随机点集下，一条空间填充曲线路径的每段长度方差很小，这意味着前 1/k 的停靠点，大致只占 1/k 的行程时间。把整条路径切成 k 段，就能直接变成 k 辆车的并行配送方案。这种轻量又易拆分的特性，让它从纸上跑进了现实里一些意想不到的场景。
最直观的一次实战发生在绘图机上。东京大学的 M. Iri 团队用它控制绘图笔走线，原来画一张大地图要 10 小时，优化后只用 0.5 小时。在美国，富尔顿县的“送餐上门”服务用它给数百名老人和病患规划每日路线，当初的系统就建在两套名片盒上。美国红十字会也借鉴这条路子，优化亚特兰大区域向各家医院的血液运输。
军用领域同样盯上了它。战略防御计划（“星球大战”计划）的承包商 TRW 公司，最终选定空间填充曲线启发式来调度天基激光的瞄准。科学家给出的理由很明确：算法分析得透彻，能并行化，而且能跑在一台可推送入轨的计算机上。兜兜转转，一条看似纯理论的空间曲线，干的都是些很燃寿命的硬活儿。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
