algorithm - 用固定大小的方 block 平铺矩形

Question

我一直在努力为以下问题寻找方便的解决方案:

假设我们有一面给定尺寸的墙和 4 种尺寸为 4 x 2、2 x 2、2 x 1、1 x 1 的瓷砖。墙的周边内有某些矩形区域不能平铺(即孔)。还有一种特殊类型的瓦片，它具有可变尺寸 A x B，其中 A < 1。如果需要，这用于将瓦片填充到矩形的边缘。

找到符合以下约束的墙砖:

1. 相同尺寸的瓷砖不能以相同的对齐方式一个放在另一个下面(即出现在下面一行的瓷砖必须移动，这样就没有间隙，看起来像相邻瓷砖之间的交叉尺寸)
2. 使用最少数量的图 block
3. 超过矩形边界的图 block 将被修剪到边缘；这样产生的不完整的瓷砖将 splinter 成更小的瓷砖；这可能涉及使用特殊的瓷砖，无论出现什么情况，它都应始终靠近矩形的边缘或孔的边缘

到目前为止，这是我尝试过的:

1. 我研究过使用多米诺骨牌拼接解决此问题的算法，但大多数人似乎并不关心拼接过程是否会产生看起来像瓷砖相交处的十字形间隙。此外，对我来说，问题似乎有点不同，因为有更多类型的瓷砖，而且矩形似乎不必完全填充(小空间可能会保留在边缘附近，这些空间将使用特殊瓷砖填充)
2. 我尝试使用带有状态节点修剪的分支定界技术生成所有可能的切片，以便仅探索添加不打破约束的切片的那些状态，但这绝对不可扩展。<
3. 我也研究了打包算法，但据我所知，这可能会导致某种平铺，其中有小的未平整的空间可以保留在墙内。

在探索上述技术时，我可能忽略了一些东西，或者没有足够的洞察力。

说了这么多，你们有什么提示或建议来解决这个问题并产生结果吗？

This is an example of a tiling which respects constraints 1 and 3, but is not optimal

Answer 1

您需要最佳平铺，还是愿意满足于“相当好”？找到最佳解决方案可能非常困难。直觉上，我会建议以下启发式:

1. Pretend there are no holes in the wall, tile with large tiles.

2. Remove all tiles which intersect with holes.

3. current_size = largest

4. For each empty space: tile as much as possible with current_size

5. current_size = the size just below current_size

6. return to 4