简介

首先，我们要衷心感谢组织者举办这次比赛。在长达两个月的比赛期间，这个问题非常深入且引人入胜。我们深感荣幸，这项工作为我们赢得了第一枚金牌。

本 write-up 的组织结构如下：

首先，我们描述用于获得最终解决方案的算法。
接下来，我们展示针对各种 N 值的最佳解决方案的代表性布局。

注意事项：因为我们使用多种算法反复 refine 当前的最佳解决方案，所以我们无法可靠地确定对于每个 N，具体是哪个过程导致了最终解决方案。

主要算法

我们的解决方案 pipeline 主要由两个步骤组成。

步骤 1：通过 Sparrow + 手动工作 + 组合探索构建结构良好的解决方案
步骤 2：通过替换部分区域迭代改进解决方案

在每个步骤中，我们还使用了相当标准的模拟退火（Simulated Annealing）过程来 refine 解决方案。

步骤 1：通过 Sparrow + 手动工作 + 组合探索构建结构良好的解决方案

Sparrow 是一个强大的开源工具（用 Rust 实现），用于 2D 不规则 strip packing。
我们使用 Sparrow 时进行了 minimal customization（除了提供初始解决方案）。由于 Sparrow 针对的是通用 strip packing，以下限制有助于促进此实例更好的结构。

将角度限制为 8 个方向：22.5, 67.5, 112.5, …, 337.5（可通过 Sparrow 中的 allowed_orientation 配置）
对于我们想要规则性的中心区域中的物品，将角度仅限制为 22.5 和 202.5
加载现有的最佳解决方案，将左/右边缘物品略微向外移动（约 0.2），然后重新运行

Sparrow 输出示例

这些设置反映了周期性放置（由角度 a° 和 180+a° 构建），以及与墙壁对齐的角度（约 23.5°）和树尖周围的角度（约 40°-50°，取决于定义）。在实践中，它们帮助搜索有效地发现结构良好的布局。

Sparrow 在小 N 时表现良好，但一旦 N 超过大约 30，其输出就变得不够充分。与运行 Sparrow 并行，我们探索了密集的规则结构；这些努力共同导致了我们采用三行周期性排列，并通过在其角落添加物品进一步增强。然后我们使用自定义 visualizer 手动 refine 解决方案。为了简化此过程，visualizer 包括数据导入、复制粘贴、范围选择、旋转和反射等功能。

三行周期性放置

添加角落

添加角落 1 添加角落 2

（以及更多模式...）

Visualizer

我们还观察到，对于某些 N，结合两个或更多规则结构可能特别有效。具体来说，我们通过以下过程实现了这一点。
作为前提，我们在以下策略下维护一个按 (width, height) 索引的放置数据库。

将宽度和高度存储在大小为 0.01 的 bucket 中
注册新放置时，在同一 (width, height) bucket 内，保留树木数量较多的放置

我们通过各种操作反复更新此数据库。

随机组合 2-3 棵树，然后通过垂直和/或水平排列它们来创建放置
选择两个放置并垂直/水平组合它们以创建新放置（还创建变体，如反射、旋转、小偏移等）
选择一个放置并运行局部搜索（类似 hill-climbing），略微扰动树木以减小整体大小

因此，由此方法 derived 的解决方案通常看起来像是几种规则模式的组合。
组合模式

步骤 2：通过替换部分区域迭代改进

在比赛的最后阶段，我们采用了一个框架，该框架以当前最佳解决方案为输入并寻求进一步改进。这个框架源于我们早期更多的手动 refine；作为使该过程在规模上可重复的实际妥协，我们实现了一个简化的自动化变体。
该过程遵循以下流程。

从某个 N' 的最佳解决方案中，指定靠近方形角落的三角形或矩形区域，并选择其中包含的 k 个物品
将这 k 个物品粘贴到 N 的最佳解决方案的角落，并按重叠面积降序移除现有物品中的 k-1 或 k 或 k+1 个物品
解决重叠并应用模拟退火

这种从另一个 N 复制粘贴的操作很少在一次尝试中产生有效的替换。在实践中，我们重复步骤 (1) 和 (2) 多次（例如约 2000 次），使用基于重叠面积的启发式方法作为主要筛选信号，仅对最有希望的候选者进行步骤 (3)。

模拟退火

整个过程中使用的模拟退火过程相当标准：每次移动略微扰动单个树的位置，没有特殊转换。因此，它作为独立求解器效果不佳；然而，它对于 refine 候选结构周围的局部最优值很有用。我们的模拟退火实现 largely standard，只有 minor（并且仍然相当 conventional）的 tweaks；为了完整性：