algorithm - block 布局算法

Question

我正在寻求帮助，以改进用于放置奇形怪状方 block 的算法。我的问题域很奇怪，但我的积木最好的类比是俄罗斯方 block ，除了它们可以有四个以上的部分。 block 仍然只由直角组成，但它们可以是长而曲折的，它们可以分支等等。

我正在尝试在最小空间内排列多个任意形状的大块(我知道，这是一个装箱问题)，但我目前的解决方案看起来很难看。我基本上是放置一个，然后通过尝试将它们放置在我的网格的原点，然后慢慢地将它们推向不同的方向，直到它们不再碰撞，从而强行强制其余的。它并不慢，但它不会尝试很好地匹配各个部分，因此它们不会浪费整体空间。

我唯一能想到的尝试是按大小对 block 进行排序，先放置最大的，然后将最小的放入最后的任何孔中。但肯定有一些方法会适得其反。

是否有任何启发式或近似算法可以帮助我解决这个问题？

结果如下所示:

另外，也许我的头像泄露了这是洛克人相关的......

Answer 1

这个(polyomino shape-packing)通常看起来是一个不平凡的数学问题，我会向您指出其他一些研究过它的人的专业知识。这个人在他的网站上有一堆 polyomino 示例，其他人可以在其中提交解决方案。他还有 Java 求解器软件:

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html .

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

Stephen Montgomery-Smith 也为此编写了一些算法，似乎比上面的更全面(它解决了一些用它无法解决的问题)最终将其变成了 xscreensaver(实际解决了-时间和冷静观看!)。以下截屏来自屏幕保护程序，仅显示五联骨牌以下的形状，但它适用于具有一般容器的一般形状。

http://www.math.missouri.edu/~stephen/software/

我不确定这些软件中的任何一个是否近似于允许漏洞的多联骨牌的最佳拟合。但这种方式绝对是“可判定的”，因为您当然可以在您的解决方案中插入额外的 1x1 多联骨牌，看看它是否能找到适合的特定结果，然后移除 1x1 多联骨牌以获得结果。

对于您的应用程序，向后工作可能更有效。所有这些算法在每个 block 中的单元格数量上都具有复杂性。布置 block 的一个好方法是将它们视为较大单元格中的“分割”，以便 block 中的 3x3 正方形对应于重新缩放版本中的 1x1 正方形。然后，用空白填充 block ，使它们都由较大的 block 组成，运行算法，并去除多余的空间。这不仅执行起来要快得多，而且还会在 block 之间生成您需要的空间。