第8名解决方案

我们，@qiaoshiji、@vialactea、@zyu2017 和 @runningz，感谢 Kaggle 团队提供了这个有趣的问题，也感谢所有的参赛者！我们的解决方案采用了相当“暴力”的方式，在这个帖子中我们将简要总结我们的思路。

正如许多其他团队所做的那样，我们首先寻找一个良好的初始 TSP（旅行商问题）路径，然后使其对配置（configuration）友好。我们的解决方案大致可以分为四个阶段：

1. 寻找一个良好的初始 TSP 路径
2. 手动冻结部分边
3. 在我们选定的边的基础上优化 TSP
4. 将 TSP 路径转换为最终解决方案

无约束的 TSP

起初我们不太确定在不考虑配置的情况下从 TSP 路径开始是否有效。然而，正如 @cnumber 在这个帖子中指出的那样，最小生成树的下界大约是 72599，而且正如 @elvenmonk 在这里提到的那样，这个界限相对宽松。我们模糊地推测 LB（排行榜）上的顶尖分数是从 TSP 路径开始的。

我们运行了几天 LKH，它给出了 74077 的解。我们也用 Cplex 运行了一些子问题，希望能得到更好的解。虽然 Cplex 因问题规模太大而无法求解，但它能非常缓慢地提升下界，最终比生成树得到的下界更紧。鉴于下界和上界之间的差距，我们确信我们可能走在正确的轨道上。

我们在 LKH 上投入了大量的计算资源，最好的解大约是 74075.3。我们获得更好 TSP 路径的“秘密武器”是 GA-EAX，这也是第1名和第4名解决方案所使用的方法。GA-EAX 最终为我们带来了一条 74074.95 的路径。

深入探索限制条件

我们推测，一旦第一个环节成功到达 (64, ±64)，就可以无代价地将 TSP 路径转换为解决方案，因为自由度非常充足。为了验证我们的假设，我们从一条直上/直下的路径开始，即起始为：
(0, 0), (0, 1), (0, 2), ... (0, 64)
结束为：
(0, -64), (0, -63), (0, -63) ... (0, 0)。

我们成功实现了这条路径，只付出了很少的额外代价。这个概念验证实验帮助我们识别了另一个限制。（我们将路径转换为解决方案的方法放在最后一节介绍。）

1. 不要用直线连接 (-127, -127), (-127, 127), (127, -127), (127, 127) 中的任意两点。（引自 @cnumber 和 @kibuna 的解决方案）
2. 不要在很短的时间内遍历所有四个象限。（我们后来发现了这个限制，但很容易修复）

手动选择起始和结束子路径

我们最好的路径（背景中的蓝色路径）向左转得太