有限制条件下的矩形排列问题

Question

我想把一组矩形（例如）打包起来： 使总高度尽可能低，但是必须满足矩形必须最终停留在它们开始的同一列中。 矩形允许“穿过”彼此以达到最终状态，只要它们在结束时不相交。

我们目前的算法是按照高度从大到小处理矩形，并将它们放在可用的最低y位置。是否存在更优算法？ 编辑： 我并不一定需要最优解，任何比当前算法生成更好的解决方案都很有趣。另外，矩形数量约为50个。

- Andreas Brinck

---

好的，我没有解决方案给你（尽管我的直觉告诉我有一个，可能与动态规划解决重叠区间的问题有关），但我可以证明你在下面的答案评论中提供的这个特定问题的解决方案是最优的：你可以轻松地证明任何解决方案的最大高度永远不会低于“一列中平方和的最大值”，因此，如果你找到一个等于它的解决方案，那么它必须是最优的。 - BlueRaja - Danny Pflughoeft

我们还可以展示您的算法不是最优解：在左边堆叠两个高度均为3的瘦长块，然后放一个高度为4的非常宽的块，最后在右边放一个高度为5的瘦长块。 - BlueRaja - Danny Pflughoeft

@Andreas 请确保不要错过我的回答 - 我花了一些时间来准备它。 :) - Timothy Shields

似乎这相当于将任务并行调度（无需上下文切换），只要它们不共享任何资源。每列代表一个资源，每个块代表一个任务，块与列相交的列表示任务必须访问的资源，块的高度是任务运行所需的时间。您的问题比这更受限制，因为您的每个对象都是连续的块（占用一组相邻的列）。不确定这个见解是否有帮助。 - mbeckish

如果您不需要最优解，那么我认为这个问题将是随机算法的一个很好的候选，例如遗传算法或模拟退火算法。 - mbeckish

可能是重复问题：https://dev59.com/XUXRa4cB1Zd3GeqPrFxA - mbeckish

Answer 1

假设您有 N 个矩形。对于每个矩形 i，让 [a_i,b_i] 表示其水平跨度，h_i 表示其高度。

您的解空间看起来像 y_i, i = 1, ..., N，其中矩形 i 的垂直跨度为 [y_i，y_i + h_i]。

不失一般性，我们可以约束 y_i >= 0。然后，我们希望最小化目标函数 max{y_i + h_i | i}。

您对不重叠矩形的限制是：

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

确定哪些 [a_i, b_i] 相互交错很容易，因此确定哪些矩形对形成这些约束条件应该是直接的。

为了消除约束中的 OR，我们可以为每个约束 k 创建二进制虚拟变量 z_k 和一个足够大的 "Big M" M 并重写如下：

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

我们可以引入一个虚拟变量H，并添加约束条件y_i + h_i <= H，这样我们就可以将目标函数重写为最小化H。

得到的优化问题如下：

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

这是一个混合整数线性优化问题。存在一些通用求解器可以直接应用于此类问题。

通常，它们会执行一些技巧，例如在算法期间放宽对z_k的二进制约束条件，将其转换为线性规划问题，从而可以非常高效地解决。

我不建议尝试重新发明这些求解器。

- Timothy Shields

---

我不建议尝试重新发明那些求解器。他并没有这样做；他在询问是否有比这更有效的方法来解决他的问题。任何（NP问题）都可以被陈述为MIP问题，但是MIP求解器旨在尝试解决NP完全问题，这意味着如果他的问题不是NP完全问题，这种方法很可能非常低效。我认为它不是NP完全问题，这将使这个答案没有什么帮助。 - BlueRaja - Danny Pflughoeft

@BlueRaja问题中的最后一句话是“是否有更优化的算法？”OP描述了他的算法是贪婪和次优的。我提供了一个给出最优解的公式 - 我会说这是“更优化的”，因为OP要求。此外，有MIP求解器将使用分支和界限技术，以便您可以获得可控的次优解。你有什么问题？ - Timothy Shields

@TimothyShields：BlueRaja的抱怨是解决一个整数线性规划(ILP)可能比这个问题需要的时间更长。我不会像你那样过分地-1你的答案，尽管它可能比必要的慢，但仍然是解决问题的相当实用的方法，但他的批评是正确的。 - j_random_hacker

@j_random_hacker：“……可能比这个问题花费更长的时间……可能比必要的慢……”——我强调了关键词：可能。BlueRaja是一个喷子。他在帮助OP方面没有提供任何有建设性的东西，而且他对一个完全有效、信息无误的答案进行了贬低（这在他通常情况下是很常见的）。任何想为这个问题贡献一个定制算法的人都可以这样做，但在此之前，我认为这是一个非常合理的解决方案。 - Timothy Shields

冷静下来。“我不建议试图重新发明这些求解器”可能具有误导性，因为它表明没有更快的算法是可能的。要实际上达到这种情况，至少需要一些证据表明问题可能是NP难的。（以同样原则的一个更极端的例子：如果问题是“如何对数字数组进行排序？”，我也可以提出一个ILP公式解决它。如果我加上“我不建议试图重新发明这些求解器”，这将是误导性的。） - j_random_hacker

Answer 2

考虑到矩形只能垂直移动，似乎只有两种解决方案：将所有矩形尽可能向上移动，直到发生碰撞；或将它们全部向下移动，直到发生碰撞。我有一种隐约的感觉，这些解决方案是等价的。当你受到一维限制时，也许没有更复杂的包装概念。也许我错过了什么吗？

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

- Gian

---

我认为你忽略了矩形可以互相穿过，只要它们之后不相交。你的解决方案基本上是让方块垂直下落，然后看它们如何安置。这不是最优解。如果你看一下上面的例子，浅蓝色的矩形可以放在底部，在大蓝色矩形下面。 - Andreas Brinck

啊，抱歉。我以为它们不能相互通过。结果这变成了一个更有趣的问题 :) - Gian

@AndreasBrinck，你应该将这个内容添加到你的问题中，而不仅仅是在评论中，这样新读者就可以理解问题，而不必阅读评论。 - Thomash

Answer 3

在我看来，第一步是计算每一列所需的最小高度。以您的图片为例，第一列至少需要高度为10，这是由红色、绿色和小蓝色矩形贡献的。这可以通过迭代每个给定的矩形并将其对应的高度添加到它所占据的列中来轻松完成。通过这样做，找到所有“列高度”中的最大值，我称之为“柱子”。在您的图片中，“柱子”位于列8:10，高度为14，由矩形1、2、4、6（从下往上编号）贡献。这意味着包装的最小高度至少是“柱子”的高度，因为“柱子”列是实心填充的，不能进一步减少。将这四个矩形堆叠起来形成这样的图片：（未显示非“柱子”矩形）

然后，柱子将图片分为两部分，一部分在柱子左侧，另一部分在另一侧。此外，“非柱子”矩形（R3、5、7、8）也分别放置在两个区域中。R3、R7在LHS上，R5、R8在RHS上。

现在先考虑左侧部分。我按照如图所示重新排列了柱子的矩形（fig.3）：

通过重新排列的柱子矩形堆叠顺序，虽然我没有严格的证明，但很可能无论什么形状和数量的矩形都可以放置在柱子左侧的空白区域中（这里的约束是这些矩形不能给出更高的实心柱子，否则步骤1会检测到并将其用作实际柱子）。此安排使得左侧的空白区域具有最佳的“空间一致性”，这意味着每个柱子矩形创建的空白空间从下往上按升序堆叠。这种“一致性”让每个柱子矩形创建的空白空间“共同工作”，然后包含比任何单个柱子矩形创建的单个空白空间更高的矩形。例如，下一个图片中的绿色矩形是使用蓝色和紫色矩形一起创建的空白空间来适应的。

假设上面的陈述是正确的，那么左边的矩形永远不会比支柱高。但是，如果这些矩形需要在左侧之间进行任何合作才能适应，则它们实际上限制了支柱矩形的交换可能性。以图3为例，绿色矩形需要紫色和蓝色相邻才能适应，然而，为了在RHS上获得最佳空间一致性，洋红色必须放在紫色和蓝色之间。这意味着LHS上的绿色使得在RHS上定位的矩形无法适应空白区域，并且超过了支柱设置的高度，从而可能导致堆叠出现孔和超过支柱高度。很抱歉我不能在这里设计这样的情况，但它确实有所不同。

总之： 第一步是找到支柱，如果每个给定的矩形都涉及支柱，则可以在此处找到一个简单的答案-支柱的高度是最小堆叠高度。

第二步是检查支柱两侧。 情况a：如果一侧没有自由矩形定位，则另一侧可以轻松地使用“最佳一致性”方法填充，从而导致最小堆叠高度再次为支柱高度。

情况b：如果一侧不需要自由空间一致性，则该侧可以填充，而另一侧仍然可以使用“最佳一致性”。例如：（您的原始图片） 在这种情况下，适合R3所需的空白空间仅由R6创建，适用于R7和R2。因此，将R6和R2的堆叠顺序与其他支柱矩形交换不会使R3，R7不适合于R3，R7遵循交换。这可以导致RHS的“最佳一致性”情况： 然后，RHS可以用RHS定位的矩形填充，而不超过支柱高度。 可以通过比较要适应的自由矩形的高度和要为其创建自由空间的支柱矩形的高度来识别不需要一致性的情况。如果自由矩形的高度不大于另一个矩形，则不需要第二个支柱矩形参与其中，这意味着它不需要自由空间的一致性。

情况c: 双方需要自由空间的一致性。这就是问题出现的地方。再以图3为例。图3中的绿色与紫色和蓝色相结合。这意味着绿色、紫色和蓝色被视为一个整体，以与其他柱形矩形交换堆叠顺序，以便得到LHS的自由矩形最佳适配。在这个整体中，蓝色和紫色也可以交换。
如果RHS无法适配，则需要重复步骤二，但先适配RHS，然后尝试适配LHS。然后将比较后的较低装载高度结果作为最终结果。对于这种情况的逻辑不清楚，极有可能有更好的替代方案。

我知道这不能算作一个合适的解决方案，而只是随意的思考，但显然它无法适应评论区。请原谅我拙劣的解释和图片处理能力。希望这可以帮到您。

- springRoll

---

忘了提到，这个“解决方案”只讨论了在第一步后仅发现一个支柱的情况。如果发现多个支柱，将第二步应用于两侧的前两个区域并不太难，然后将前两个区域作为整体应用第二步于下一个区域。这会导致更加混乱的交换和跟进。 - springRoll