块布局算法

Question

我正在寻找帮助改进放置奇怪形状块的算法。我的问题领域很奇怪，但我最好的比方是俄罗斯方块，除了他们可以有四个以上的东西。块仍然是只有直角组成，但他们可以是长期和缠绕，他们可以分支等

我想安排在最小的空间多个大型任意形状的块（我知道，一个装箱问题），但我目前的解决方案看起来很丑。我基本上是放置一个，然后通过尝试将它们放在我的网格的原点，然后缓慢地将它们推向不同的方向，直到它们不再碰撞为止，然后蛮力强制其余的。虽然速度并不慢，但它并没有试图很好地装饰件，所以它们不会浪费整体空间。

我能想到的唯一的尝试是按大小排序块，放置最大的块，然后将最小的块放入剩余的任何洞中。但肯定会有适得其反的方法。

有没有可以帮助我的启发式算法或近似算法？

结果将类似于以下内容：

而且，也许是我的gravatar赠送，这是相关的洛克人...

Answer 1

这（四角形状包装）一般似乎是一个不平凡的数学问题，我会告诉你一些其他人的专业知识。这家伙在他的网站上有一些polyomino的例子，其他人可以提交解决方案。他还有Java中的解算器软件：

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

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

还有斯蒂芬·蒙哥马利 - 史密斯，这个写了一些算法，它似乎比上述更全面（它解决了一些问题，这些问题不解决的与）最终使它成为一个xscreensaver（实时解决和酷观看！）。屏幕保护程序中的以下屏幕截图只显示了五角形的形状，但它适用于一般容器的普通形状。

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

我不能确定，如果这两种软件的近似四角系统允许孔的最佳选择。但是这种方式绝对是“可判定的”，因为您可以将额外的1x1多米诺骨牌插入您的解决方案，并查看它是否能找到适合的特定结果，然后移除1x1碎片以获得结果。

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