第4名解决方案

首先，我要感谢 Kaggle 举办这一年一度的圣诞老人比赛。我每次都很享受这个比赛。

这是一个可以在短时间内运行我的解决方案的 Notebook，得分为 74083。

请注意，在我的解释中，从上数第 y 个（0-indexed，即从0开始计数）、从左数第 x 个像素表示为 (y, x)。中心像素是 (128, 128)。

我的解决方案是使用 Concorde 和遗传算法求解受约束的 TSP（旅行商问题），然后将生成的路径转换为机械臂的配置。

在详细描述解决方法之前，我将解释为了得出这个解决方法所必须进行的考量。

初步观察与考量

首先，一些实验表明了以下几点：

• 机械臂的自由度足够高。例如，给定一个随机像素和一个指向该像素的随机配置，我们仅移动其中一个手臂就能移动到其右侧像素的概率相当高。

由此可知，正如讨论中已经指出的那样，首先解决 TSP，然后构建配置以遵循该路径是一个有效的策略。

然而，将纯粹解决 TSP 获得的解直接转换为配置似乎并不奏效。

我认为这很大程度上是由于最长臂的限制。例如，最初最长臂是向右伸直的。由于当最长臂指向右侧时无法打印卡片的左侧，因此 x < 128（左半部分）的区域必须在最长臂从初始状态向上（或向下）移动至少 64 次之后才能绘制。

此外，除了最长臂的限制外，似乎还有三种情况会阻碍构建高效的配置：

1. 过早尝试绘制 x < 128 的区域
   • 这与上面的例子相同，但实际上比仅考虑最长臂时的限制稍微严格一些。
2. 过早向右移动太远
   • 例如，由于初始配置中所有臂都指向左或右，第一步移动仅限于上或下，向右移动是不可能的。（最长臂的限制已经排除了向左的选项。）
   • 如果在第一步使用最短的臂向上或向下移动，则可以进行两次向右移动，但是，三次移动，即从初始状态开始的“下→右→右→右”，仍然是不可能的。
3. 沿着外边缘的第二个像素移动
   • 可能是由于调整图像大小的算法存在错误，最外层的像素比其他像素暗，而第二外层的像素比其他像素亮，因此纯粹的 TSP 解会包含沿着它的路径。其中，像第二外层那样的“冖”形路径（例如：(2, 1) → (1, 1) → (1, 2) → … → (1, 254) → (1, 255) → (2, 255)）无法用于构建高效的配置。（TSP 的成本与臂移动的成本无法匹配。）

解决方案详情

基于上述考量，我能够使用下面描述的方法达到 74075.7065416901 的分数。

首先，使用遗传算法（GA）求解 TSP。
此时，处理的路径始终是可构建配置的。也就是说，每次生成新路径时，都会执行以下检查，如果结果为 False，则立即消除该路径。

def is_valid_tour(tour):
    if not simulate_longest_arm(tour):
        return False
    if left_side_pixel_in_beginning_or_end(tour):
        return False
    if far_right_pixel_in_first_or_last_paths(tour):
        return False
    if has_冖(tour):
        return False
    return True

simulate_longest_arm() 使用动态规划计算最长臂在路径上向下移动时是不动还是向下移动一个单位。（其他方向同理。）

初始路径生成

GA 的第一代路径是通过以下过程生成的：

1. 以某种方式创建满足上述条件的路径。
2. 从路径中提取最多约 2400 个顶点，并反复用 Concorde 求解的 TSP 解替换它们。（如果替换后的路径未通过 is_valid_tour() 检查，则不替换。）

在步骤 2 中，除了提取路径中第