algorithm - 带约束的矩形包装

Question

我想打包一组矩形（示例）：

因此，总高度尽可能低，并限制矩形必须在它们开始的同一列中结束。 允许矩形相互“移动”以达到最终状态，只要它们不' t 最后相交。

我们当前的算法是从最大高度到最小高度处理矩形，并将它们放在可用的最低 y 位置。有没有更优化的算法？

编辑：我不一定需要最佳解决方案，任何产生比当前解决方案更好的解决方案的算法都很有趣。此外，矩形的数量约为 50。

Answer 1

Suppose you have N rectangles. For each rectangle i, let [a_i, b_i] be the horizontal span, and let h_i be the height.

Your solution space looks like y_i, i = 1, ..., N, where the vertical span of rectangle i is [y_i, y_i + h_i].

Without loss of generality, we can constrain y_i >= 0. We then want to minimize the objective function max{y_i + h_i | i}.

The constraints you have for non-overlapping rectangles are:

y_i + h_i <= y_j
   OR
y_j + h_j <= y_i

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect

Figuring out which [a_i, b_i] intersect with each other is easy, so figuring out for which pairs of rectangles to form these constraints should be straightforward.

To get rid of the OR in our constraint, we can create binary dummy variables z_k for each constraint k and a "Big M" M that is sufficiently large and rewrite:

y_i + h_i <= y_j + (z_k)M
y_j + h_j <= y_i + (1-z_k)M

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect

We can introduce a dummy variable H and add the constraints y_i + h_i <= H so that we can rewrite the objective function as minimizing H.

The resulting optimization problem is:

minimize H
with respect to: y_i, z_k, H
subject to:

 (1) y_i + h_i <= y_j + (z_k)M    for all i != j such that [a_i, b_i]
     y_j + h_j <= y_i + (1-z_k)M  and [a_j, b_j] intersect

 (2) y_i + h_i <= H               for all i

 (3) y_i >= 0                     for all i

 (4) z_k in {0, 1}                for all constraints of type (1) k

This is a mixed-integer linear optimization problem. There are general solvers that exist for this type of problem that you can apply directly.

Typically, they will perform tricks like relaxing the binary constraint on z_k to the constraint that z_k be in [0,1] during the algorithm, which turns this into a linear programming problem, which can be solved very efficiently.

I would not advise trying to reinvent those solvers.

Answer 2

鉴于矩形只能垂直移动，似乎只有两种解决方案：将所有矩形尽可能向上移动直到发生碰撞，或者将它们全部向下移动直到发生碰撞。我暗中怀疑这些解决方案将是等效的*。当您被限制在一维时，我认为没有更复杂的包装概念。也许我错过了什么？

*如果我正确理解了您的约束，则最小高度将始终是填充单元格数量最多的列中填充单元格的数量。无论翻译是向上还是向下应用，这都不会改变。

Answer 3

在我看来，第一步是计算每一列的最低要求高度。以您的图片为例，第一列需要至少 10 的高度，这是由红色、绿色和蓝色小矩形贡献的。这很容易通过遍历每个给定的矩形并将其相应的高度添加到它所占据的列来完成。通过这样做，可以找到所有“柱高”中的最大数，我称之为“柱子”。在您的图片中，“支柱”位于 8:10 列，高度为 14，由矩形 1、2、4、6（从下到上编号）贡献。这意味着填料的最小高度至少是“柱”的高度，因为“柱”柱是实心填充的，不能进一步减小。

然后柱子将图片分成两部分，一个是柱子左边的区域，另一个是柱子的另一边。此外，“非支柱”矩形 (R3,5,7,8) 也分别定位到这两个区域。LHS 上的 R3、R7 和 RHS 上的 R5、R8。

现在首先考虑左侧部分。我重新排列了柱状矩形，如图所示（图 3）：

使用重新排列的柱子矩形堆叠顺序，虽然我没有严格的证据，但很有可能无论柱子的 LHS 上放置什么形状和数量的矩形，所有给定的矩形都可以适合在 LHS 上的空白处（这里的限制是这些矩形不能提供更高的实心柱子，否则步骤 1 会已经检测到并将其用作实际的柱子）。这种安排使 LHS 上的空白空间具有最佳的“空间一致性”，这意味着每个柱状矩形创建的空白空间从下到上按升序堆叠。这种“一致性”让每个柱状矩形创建的空白空间“一起工作”，然后包含比单个柱状矩形创建的任何单个空白空间更高的 retangles。

假设上面的陈述是正确的，那么位于 LHS 上的矩形将永远不会比柱子堆得更高。但是，如果这些重新排列需要空白空间之间的任何合作以适应 LHS，那么它们实际上会限制柱状矩形的交换可能性。以图 3 为例，绿色矩形需要紫色和蓝色相邻才能适应，但是，为了在 RHS 上获得最佳空间一致性，洋红色必须介于紫色和蓝色之间。这意味着 LHS 上的绿色使得 RHS 无法获得最佳一致性，因此可能使位于 RHS 上的矩形无法放入空白空间并导致堆叠有孔并超过支柱设置的高度。抱歉，我无法在这里设计这样的案例，但它确实会有所作为。

总结：
第一步是找到柱子，如果每个给定的矩形都包含在柱子中，则可以在这里找到一个简单的答案——柱子的高度是最小包装高度。

第 2 步是检查柱子的两侧。
案例a：如果一侧没有放置自由矩形，则可以使用“最佳一致性”方法轻松填充另一侧，并且得到的最小包装高度再次成为支柱高度。

案例b：如果一侧不需要可用空间一致性，则可以填充该侧，而另一侧仍然可以使用“最佳一致性”。例如：（您的原始图片）

在这种情况下，安装 R3 所需的空白空间由 R6 单独创建，R7 和 R2 相同。因此，如果 R3、R7 跟随交换，将 R6 和 R2 的堆叠顺序与其他柱状矩形交换不会使 R3、R7 不合适。这可能会导致 RHS 的“最佳一致性”案例：

然后可以在不超过柱高的情况下用 RHS 定位的矩形填充 RHS。
这种不一致的要求可以通过比较要适应的自由矩形的高度和为其创建自由空间的柱状矩形的高度来识别。如果空闲矩形的高度不大于另一个，则不需要第二个柱状矩形参与，这意味着它不需要可用空间一致性。

案例c：双方需要自由空间一致性。这就是麻烦开始的地方。再次以图3为例。图 3 中的绿色结合了紫色和蓝色。这意味着绿色、紫色和蓝色被视为一个整体，以与其他支柱矩形交换堆叠顺序，以使 LHS 的空闲矩形最适合。而在这个整体中，蓝色和紫色也可以互换。
如果RHS无法配合，导致包装高度大于支柱高度，则需要重复第二步，但先安装RHS，然后再尝试安装LHS。然后将比较的较低包装高度结果作为最终结果。这种情况的逻辑不清楚，很有可能有更好的替代方案。

我知道这不应该被称为一个适当的解决方案，而是随机和松散的想法，但它显然不适合评论。请原谅我笨拙的解释和糟糕的图片处理。希望这可以帮助。