一秒规划德国1.5万城市路线

Some combinatorial applications of spacefilling curves

空间填充曲线（Spacefilling curves）不仅是数学奇景，更是解决旅行商问题（TSP）的高效利器。通过Sierpinski曲线，我们能在O(n log n)时间内为随机点集生成路径，虽比最优解长约25%，却无需计算距离且支持并行。从Fulton County的Meals-on-Wheels送餐，到美国红十字会（American Red Cross）的血液配送，再到战略防御计划（SDI）的激光瞄准，这一启发式算法已广泛应用。对比Applegate等人耗时22.6年CPU时间算出的德国15,112城市最优解，我们的算法仅需不到一秒，虽多跑约34%路程，却实现了即时响应。