Santa25 第 12 名
引言
首先，我们团队要感谢组织者使这次比赛成为可能。同时，我们要感谢在比赛期间分享原始想法、发现和代码的参与者。这是一次有超过 3300 支队伍参加的比赛，我们很高兴能获得第 12 名。
我们最终结果的关键要素：
- 使用模拟退火和模因算法进行优化的高效代码
- 积极使用 Spyrrow/Sparrow 代码
- 使用 Spyrrow 为大 N 值构建初始猜测的方法，效果很好。在这种方法中，树晶格被替换为凹包，然后在 Spyrrow 优化期间被视为单个多边形。更多信息请参考 详情 部分。
- 使用纵横比扰动方法避免当前局部最小值的方法。具体来说，我们从当前纵横比为 1 的正方形解开始。然后，我们将此解优化到 0.9-1.1 的纵横比，再回到纵横比 1。我们在这些步骤中使用了模因算法，这对于此目的在计算上是高效的。在这种扰动之后，应用模拟退火。这种方法在整个比赛中效果很好。
- 将得分高的树布局转移到其邻居。例如，通过从良好的 N 树解中移除一棵树来构建 (N-1) 树解的初始猜测。移除的树可能是边界树或周围有较大空间缓冲的树。类似地，可以通过向良好的 N 树解添加一棵树来构建 (N+1) 树解的初始猜测。添加树的最佳位置可以通过检查 (N+1) 树配置的结果得分来确定。
详情
小 N 的解决方案
对于小 N，我们简单地使用 Spyrrow 对多个种子预优化解。然后，对于得分好的解，我们应用模拟退火。Spyrrow 请求的条带高度根据当前考虑的 N 所取得的得分逐渐减小。
大 N 的解决方案
我们许多大 N 的解由一个大的晶格部分和位于一侧或两侧相连边上的自由树带组成。下图提供了 N = 128, 132, 181 和 192 的此类解示例。
我们找到了一种使用 Spyrrow 构建此类解初始猜测的有效方法。首先，构建所需大小的晶格部分。其次，将晶格部分替换为凹包表示，使其在 Spyrrow 优化中被视为单个对象。然后使用 Spyrrow 在构建的凸包表示附近/周围放置自由树。最后，将凹包替换回晶格树，生成的树配置作为后续使用模拟退火优化的初始猜测。下图说明了这个过程。
Spyrrow 优化需要对请求的条带高度进行一些实验，以及尝试多个种子。这些解中使用的树晶格参数是通过最小化两个垂直平移向量的乘积来确定的。此优化产生了具有垂直平移向量的无限树晶格的最密配置。
另一种在大 N 上取得好得分的解类型也在中心区域包含一个树晶格块。非晶格树位于角落附近以及沿着一侧或两侧相对的边。下图提供了 N = 88, 115, 159 和 170 的此类解示例。
对于这类解，我们没有精确的策略来准备初始猜测。此类解是在某些 N 的优化过程中出现的，然后使用引言中简要描述的策略转移到相邻的 N-1 和 N+1 解。引言中描述的纵横比扰动方法对于这类解特别有效。
最后，我们可以看看我们得分最高的两个解，它们的得分都是 0.328x，但对应不同的树布局。
