块布局算法(Block layout algorithm)

我在寻找与改善放置不规则形状的块的算法的帮助。我的问题域奇怪，但对我的块最好的比喻是俄罗斯方块件，但他们可以有超过四个。块仍然是仅由直角的，但它们可以是长期的，缠绕，它们可以分支等

我想安排多个大型任意形状的块在最小的空间（我知道，一个装箱问题），但我目前的解决方案看起来丑陋。我基本上把一个，然后用蛮力试图把它们放在我的网格的原点，然后慢慢推他们在不同的方向，直到他们再也不会发生碰撞强制休息。这是不慢，但它不会使任何企图以适应件很好地使他们不浪费整体空间。

我能想到的尝试的唯一的事情是由大小排序的块，将最大的第一，然后安装在最小的一端插入剩余的任何漏洞。但也有肯定的是可能会适得其反方式。

是否有任何启发式或者近似算法，可以帮助我在这里？

结果将类似于以下内容：

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

这（四角形状包装）通常似乎是一个平凡的数学题，我会点你一些其他人谁已经在它的工作的专业知识。这家伙有一堆在他的网站，别人可以提交解决方案四角的例子。他还对Java的求解软件：

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

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

还有斯蒂芬·蒙哥马利 - 史密斯，这个写了一些算法，它似乎比上述更全面（它解决了一些问题，这些问题不解决的与）最终使它成为一个的xscreensaver（实时和冷静解决了观看！）。下面的截图，从屏幕，只能显示形状高达pentominoes，但它的工作原理与普通的容器一般形状。

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

我不能确定，如果这两种软件的近似四角系统允许孔的最佳选择。但是，这绝对是“可判定的”这样，你当然可以插入额外的1x1的四角系统到您的解决方案，看看它是否能找到一个适合，然后删除1x1件得到的结果特定结果的意义。

对于您的应用程序，它可能是更有效的逆向操作。所有这些算法中的单元电池的每个块中的数具有的复杂性。奠定了你的砌块的好方法是将它们看作是在较大的细胞“细分”，让你的块一个3x3正方形对应于在重新缩放版本一个1x1正方形。然后，垫空的空间，所以它们都包含较大块的块，运行算法，并夺走了额外的空间。这不仅是更快的执行，但它也将产生你所需要的块之间的空间。