我正在寻求帮助以改进放置奇怪形状块的算法。我的问题域很奇怪，但我的块最好的类比是俄罗斯方块，除了它们可以有四个以上。这些块仍然仅由直角组成，但它们可以是长而弯曲的，它们可以分支，等等。
我试图在最小的空间中安排多个任意形状的大块（我知道，一个装箱问题），但我目前的解决方案看起来很难看。我基本上是放置一个，然后通过尝试将它们放置在我的网格的原点来强制其余的，然后慢慢地将它们推向不同的方向，直到它们不再碰撞。它并不慢，但它并没有尝试很好地安装部件，因此它们不会浪费整体空间。
我唯一能想到的尝试是按大小对积木进行排序，首先放置最大的，然后将最小的放在最后的任何孔中。但肯定有一些方法会适得其反。
有什么启发式或近似算法可以帮助我吗？
结果如下所示：
另外，也许我的 gravatar 表明这与洛克人有关……
这个（polyomino shape-packing）通常似乎是一个不平凡的数学问题，我将向您指出其他一些研究它的人的专业知识。这个人在他的网站上有一堆多米诺骨牌示例，其他人可以在其中提交解决方案。他还拥有 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 正方形。然后，用空白空间填充块，使它们都包含较大的块，运行算法，并去除多余的空间。这不仅执行起来要快得多，而且还会在您需要的块之间生成空间。
有趣的问题。
定义一个势场，因此每个单元格对其他所有单元格都有引力。另外，对相邻小区之间的刚性关系有严格的限制。可选地附加排斥力，可能基于距离的立方。这样，远处的方块就会相互吸引，直到它们遇到一个阻止它们相互接触的区域。
定义了这样一个场之后，让每个块找到它的局部梯度并平滑地向下滑动就很简单了。
局部最优是可能的。以不同的起始位置重新运行几次。您需要定义一个目标函数，该函数可以对竞争提出的解决方案进行排序。
您还可以暂时在某个随机位置插入一个排斥场，以使块脱离局部最优。