用最少数量的盒子填充空间的任何算法

Question

让 3D 网格就像棋盘一样，具有额外的维度。现在假设我在该网格中有一定数量的立方体，每个立方体占据 1x1x1 个单元格。假设每个立方体都是一个项目。

我想做的是将这些立方体替换/组合成更大的盒子，占据 X、Y 和 Z 轴上任意数量的单元格，以便生成的盒子数量尽可能小，同时保留整体“外观”。

可能还不清楚，所以我举一个 2D 的例子。假设我有一个 2D 网格，其中包含几个占据 1x1 单元格的正方形。字母代表给定项目占据的单元格，每个项目具有与其他项目不同的字母。在第一个示例中，我们有 10 个不同的项目，每个项目占用 1x1x1 个单元格。

+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | B | C | D |   |
+---+---+---+---+---+---+
|   | E | F | G | H |   |
+---+---+---+---+---+---+
|   |   | K | L |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+

这是我的输入数据。我现在可以优化它，即通过多种可能的方式减少项目数量，同时仍然占用相同的单元格，其中之一可能是：

+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | B | B | C |   |
+---+---+---+---+---+---+
|   | A | B | B | C |   |
+---+---+---+---+---+---+
|   |   | B | B |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+

在这里，我只有 3 个（即 A、B 和 C），而不是 10 个项目。然而它还可以进一步优化：

+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | A | A | A |   |
+---+---+---+---+---+---+
|   | A | A | A | A |   |
+---+---+---+---+---+---+
|   |   | B | B |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+

这里我只有两个项目，A 和 B。这是尽可能优化的。

我正在寻找一种能够找到最佳项目大小和排列的算法，或者至少是一个相当好的算法，这样我在占据相同单元格的同时，在 3D 中拥有尽可能少的项目！

有这样的算法吗？我确信这种算法在某些领域会很有用，而且我需要它来制作视频游戏。谢谢 ！！

Answer 1

也许可以使用更简单的算法，但设置分区就足够了。

Min       x1 + x2 + x3 + ... //where x1 is 1 if the 1th partition is chosen, 0 otherwise
such that x1 +    + x3 = 1// if 1st and 3rd partition contain 1st item
               x2 + x3 = 1//if 2nd and 3rd partition contain 2nd item and so on.

          x1, x2, x3,... are binary

每个项目都有 1 个约束。每个约束都规定每个项目只能是一个盒子的一部分。目标是最小化盒子的总数。

然而，这是一个 NP 硬整数规划。

这个问题中的变量数量可能是指数级的。您需要有一种有效的方法来枚举它们——即确定何时可以找到一个能够包含其中所有点的连续框。在这里，您必须考虑网格是 2d 还是 3d、如何定义连续的“盒子”等信息。

此类问题通常通过列生成来解决，其中整数程序的这些列是动态生成的。