块布局算法

Question

我正在寻找帮助改进放置奇怪形状块的算法.我的问题领域是奇怪的,但我的块的最佳类比是俄罗斯方块,除了它们可以有超过四件.块仍然只是由直角组成,但它们可以很长而且缠绕,它们可以分支等.

我试图在最小的空间内安排多个大型任意形状的块(我知道,bin-packing问题),但我目前的解决方案看起来很难看.我基本上放置一个,然后通过试图将它们放置在我的网格的原点然后慢慢地将它们推向不同的方向,直到它们不再发生碰撞来强制其余部分.它并不慢,但它没有任何尝试很好地适应它们,所以它们不会浪费整体空间.

我唯一能想到的就是按尺寸排序块,先放置最大的块,然后将最小的块放入最后的剩余孔中.但肯定有些方法会适得其反.

是否有任何启发式或近似算法可以帮助我？

结果将如下所示:

此外,也许我的gravatar放弃了这是Mega Man相关的......

Answer 1

这个(多面体形状包装)通常似乎是一个非常重要的数学问题,我会指出一些其他人的专业知识.这个人在他的网站上有一堆多米诺骨牌的例子,其他人可以提交解决方案.他还有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碎片以获得结果.

对于您的应用程序,向后工作可能更有效.所有这些算法都具有每个块中单位单元数量的复杂性.布置块的一个好方法是将它们视为较大单元格中的"细分",这样块中的3x3正方形对应于重新缩放版本中的1x1正方形.然后,用空的空间填充块,这样它们都包含更大的块,运行算法,并去掉额外的空间.这不仅会更快地执行,而且还会在您需要的块之间生成空间.