第二名方案

大家好！

首先，我要感谢 Kaggle 团队举办这次精彩的挑战赛！我认为这次比赛的校准非常到位，工作过程充满乐趣。我真的很喜欢那个机械臂的扭转设定，它给问题增加了一层很好的复杂性。向创建者致敬！

祝贺 C-number 和 Kibuna 率先达到了局部（？）最优解！我晚了 48 小时才达到。如果我早点开始合并我的解决方案，我可能会更早发现它，但当时我没料到有人会这么快达到最优解。Newtonians 干得漂亮！同时也祝贺 Rafbill 取得了令人印象深刻的先发优势，以及所有让这次比赛变得有趣和令人兴奋的 Kagglers！😊

主要步骤

1. 我首先尝试直观地掌握机械臂的运动。乍一看，它类似于通常的 \( L^2 \) 问题，但事实证明，由于缺乏旋转对称性（这里我们只有 \( \mathbb{Z}^2 \) 格的对称性），执行逆运动学要棘手得多。我发现我喜欢把机械臂看作某种嵌套的滑块拼图。这种观察机械臂运动的方式确实帮助我弄清楚了使路径“可提升”所需的条件。

2. 从一开始就很清楚，配置空间太大，无法直接处理。因此，正如我猜测大多数参赛者所做的那样，我选择将问题分解为：
(i) 在图像空间上寻找低成本路径（针对 \( \sqrt{L^1} + \hbox{color} \) 距离）。
(ii) 将此路径从图像空间提升到配置空间，且增加的额外成本最小。

起初，我认为从 到 会产生一些成本，因为需要重新配置机械臂以获得有效解，但最终证明，直接在图像路径上添加约束以便可以无额外成本地提升它更为有效。

3. 通过观察排行榜（LB），我很早就意识到图像空间路径和配置空间路径之间的成本差异应该非常小。确实，比赛开始几天后，LB 上的分数比我生成的最佳 TSP 路径仅高出几十分。所以我开始尽可能多地生成图像空间上的 TSP 路径。我想它们以后可能会有用……在那段时间里，我寻找了一种将路径从图像空间提升到配置空间的方法。

4. 我花了一些时间才找到一种有效的方法将路径从图像空间转换为配置空间。我曾考虑使用 MIP 求解器来完成该任务，但我对这些工具不熟悉，而且我更喜欢编写代码。相反，我用 C++ 编写了一个自定义程序。在我 4 年前的 Ryzen7 台式机上，将图像空间上的路径转换为有效解通常需要不到 15 分钟（前提是路径确实可提升）。这当然可以改进，但足以满足我的需求。有关程序/算法的更多详情，请参阅下文A段落。

5. 一旦我有了一种将图像路径转换为解决方案的可靠方法，我就开始研究如何最小化重新配置成本。最终，我发现“可提升”是一个相当软性的要求。大多数硬性约束位于原点周围，即路径的开头和结尾，因为 \( (0,0) \) 处有指定的机械臂配置。特别是，最重要的约束涉及路径在半空间 \( x\geq 0 \) 中的第一次/最后一次游历的持续时间。通过反复试验，我想出了一套使路径可提升的必要（且大部分充分）条件。有关更多详情，请参阅段落B。

6. 我将这些条件作为“惩罚项”整合到一个自定义 TSP 求解器中，该求解器是 LKH3 和我为“Santa Prime Maths 2018 挑战赛”从头编写的纯 C++ TSP 求解器的混合体。在缓慢增加惩罚的同时运行此 TSP 求解器，我获得了分数约为 74076 的“可提升”路径。

7. 最后的冲刺是通过使用我在挑战赛最初几周收集的所有（大部分无约束）路径获得的。我使用 IPT 合并和一些有限的遗传算法达到了 74075.706541 的最终分数……事实上，一旦我开始合并路径，解决方案很快就出现了：我想从 76 到 75.706541... 只用了不到 30 分钟。

A. 将路径从图像空间提升到配置空间

我很快就会在我的 GitHub 页面上提供“提升”程序的代码供感兴趣的人使用（但请注意代码非常乱，抱歉……）。

给定图像空间上的路径，我们可以将路径分解为 5 部分 \( A,B,C,D,E \)，使得：

$$ (0,0) \overset{A}{\longrightarrow} \hbox{角点 1} \overset{B}{\longrightarrow} \hbox{角点 2} \overset{C}{\longrightarrow} \hbox{角