用固定尺寸的瓷砖铺设矩形

Question

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

假设我们有一个给定大小的墙壁和4种类型的瓷砖，分别为4 x 2、2 x 2、2 x 1、1 x 1。墙壁的周长内有某些矩形区域不能铺瓷砖（即孔洞）。还有一种特殊的瓷砖，其尺寸为A x B，其中 A < 1。如果需要，这种瓷砖用于填充到矩形的边缘。

查找符合以下约束条件的墙壁铺砖方案：

1. 不能将相同大小的瓷砖放置在彼此下面，且对齐方式相同（即出现在下一行的瓷砖必须被移动，以避免出现看起来像相邻相同大小的瓷砖之间的十字形缝隙）
2. 使用最少数量的瓷砖
3. 超出矩形边界的瓷砖将被修剪到边缘；因此产生的不完整瓷砖将被分成更小的瓷砖；这可能涉及到一种特殊的瓷砖，它应该始终位于矩形或孔洞边缘的旁边，无论情况如何

以下是我迄今为止尝试过的内容：

1. 我研究了使用多米诺骨牌平铺解决此问题的算法，但大多数似乎并不关心平铺过程不能产生看起来像十字交叉的间隙。此外，对我来说，这个问题似乎有点不同，因为有更多类型的瓷砖，并且矩形似乎不必完全填充（可能在边缘附近会留下小空间，将使用特殊瓷砖填充）。
2. 我尝试使用分支和界限技术生成所有可能的平铺，以状态节点修剪，以便只探索添加不违反约束条件的瓷砖的状态，但这绝对不可扩展。
3. 我还研究了装箱算法，但据我所知，这可能会导致某种平铺，其中可以在墙的范围内保留小未铺设的空间。

我可能忽视了一些东西，或者在探索上述技术时没有足够的见解。

总之，你们有什么提示或建议，可以用一种产生结果的方式来处理这个问题吗？

这是符合约束条件1和3但不是最优的平铺示例

- filipcampeanu

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

- mitchus

---

这种方法的问题在于填充剩余空间时会变得复杂。需要找到第一个放置位置，以避免形成十字形（+）。当然，这取决于你如何进行第一次平铺。由于第一次平铺的方式不同，可能存在无法进行这样的平铺的情况。还有一些情况，其中孔彼此靠近，这使您将它们视为联合案例，从而增加了搜索空间。 - filipcampeanu