algorithm - 精确覆盖问题。几何图形中的四联骨牌

Question

我正在尝试使用 algorithm X解决问题。我认为这个问题可以表示为精确覆盖问题，但我不确定。

这里是:做一组 tetrominos可以适合特定的几何图形。例子:

例子是两个“duominos”，需要放在矩形中。我看到 pentaminos problem是精确覆盖问题的一个著名例子。但在这里我并不是要“完全覆盖”矩形，我想知道我的作品是否适合矩形，当然还有哪种配置。

对于pentaminos problem ，图中的元素是宇宙，集合的集合是五元组。但这是我的问题....对于我的问题，我不想绝对填充图中的所有元素，我只想将我的所有部分放入我的图中。

我的想法是将作品视为宇宙(因为我想“覆盖”我的所有作品)，并将我的图形元素视为集合集。

也许这真的很愚蠢而且不可能，但是有人知道如何为这个问题构建算法 X 中所需的矩阵吗？

Answer 1

作为宇宙的四联骨牌

假设我们有一个 T 形四联骨牌和一个 2x3 的区域，我们希望将其放入其中。我们可以通过为四联骨牌的每个部分分配一个数字并为每个可能的覆盖集分配一个字母来确定部分覆盖集。

A [1][2] 3      B [ ][1]      C  [1][ ]
  [ ][4]          [4][2]        4[2][ ]
  [ ][ ]          [ ][3]         [3][ ]

然后，在您的矩阵中，您可以将 A1 设置为 1，因为方框 A 包含四联骨牌第 1 部分。您可以将 A3 设置为 0，因为方框 A 不包含四联骨牌部分 3。

    1  2  3  4
A [ 1  1  0  1 ]
B [ 1  1  1  1 ]
C [ 1  1  1  0 ]

您最终会在矩阵中得到 box_area * piece_orientations 行，您可以利用盒子和四联骨牌的对称性来减少这些行。但是，您不需要使用算法 X。您只需要检查并查看是否有任何行没有零，这就是您的解决方案

作为宇宙的盒子

如果您使用盒子作为您的宇宙，算法 X 将尝试找到将完全覆盖盒子的四联骨牌组合，这不是您想要做的。

---

算法 X 不太适合这项任务。该算法旨在找到合适的集合组合来覆盖整个宇宙。您正试图找到一个覆盖整个宇宙的集合(盒子)(四联骨牌)。

你的问题实际上更像是一个包装问题，而不是一个精确的封面问题。如果您试图将多个四联骨牌放入一个盒子中，则可能是包装问题或确切的封面问题，具体取决于您是否允许盒子中有任何空间。