Santa25 第 8 名

引言

首先，我要感谢组织者使这次比赛成为可能。我还要感谢其他参赛者的想法，特别是 spyrrow/sparrow 的创作者。你可以在最后的“项目文件”中找到我的 submission.csv。

解决方案概述：

• 一个用于可视化、选择和操作树的 Web 界面
• 设计不同的瓦片图案以覆盖大多数大 N 的解空间
• 对于小 N 使用 spyrrow（未修改），对于大 N 填补剩余情况
• 开发一个计算任意形状区域确切轮廓/外形的工具
• 使用模拟退火 (SA) 优化解决方案

硬件与流程：

我使用笔记本电脑管理图形界面、连接其他机器并管理进程。在两台拥有 128 线程的机器上，spyrrow 在两个单独的队列上持续运行以模拟案例。这些模拟的结果被发送到另一台拥有 24 线程的机器，该机器负责管理运行模拟退火 (SA) 的队列。

工作流程涉及逐步调试不同的配置，选择它们的子集，计算它们的确切轮廓，并指示 spyrrow 放置剩余的树——有时添加或移除树以便导出 N 棵树到 N ± n 的配置（这通常使得改变初始平铺成为可能）。

Web 界面

Web 界面允许我查看配置，使用两个窗口相互比较，选择树，旋转它们，删除它们等。最重要的是，它帮助我选择一个候选子集（由于局部密度低）以便移除，然后使用 spyrrow 重新填充。

不同瓦片图案的设计

我投入了大量时间设计具有不同标准（密度、纵横比、角度、基本形状等）的瓦片图案，并将它们用作解决方案的起点。

使用 spyrrow（未修改）处理小 N 以及填补大 N 的剩余情况

根据我的经验，spyrrow 生成的解决方案方差很大，因此运行多次模拟很有用，因为偶尔我们会得到一个优异的 outlier 结果。

开发计算任意形状区域确切轮廓/外形的工具

我使用了选择一个树子集并将其视为单个形状的想法，用于 spyrrow，由其顶点定义。我最初使用 alphashape 来定义轮廓/外形——通过调整 alpha 参数你可以获得更好的轮廓——但我对结果并不完全满意，

所以我开发了自己的任意形状轮廓评估器：

通过这种方式，我获得了这样的解决方案，结合了平铺核心和外围的孤立树：

使用模拟退火 (SA) 优化解决方案

流程的最后一步是使用模拟退火 (SA) 优化解决方案：所有从 spyrrow 出来的东西都被推入队列并用 SA 进行优化（事实上，我有两个具有不同 SA 参数设置的队列，并根据某些标准将解决方案从一个移动到另一个）。