4

假设一个布尔数组，如：

1111
1111
1110
1111
1001

现在你需要找到排列任意大小的最小矩形的方法来实现这个形状。因此，例如，您会发现：

+-++
| |+
| |
+-++
+  +

其中 + 是矩形的角，|, - 矩形的边框。

我想做的是从最大可能的矩形开始，检查数组中是否有可以放置的位置，矩形覆盖的每个数组元素都是真的。如果存在这样的地方，则该矩形将被添加到列表中。之后，我们检查数组的左侧空间是否有另一个位置可以放置矩形，然后减小矩形的大小并使用剩余空间重复该过程，直到大小为 0。

这应该会产生很好的结果，因为我们总是从大矩形开始，我们当然可以使用更少的矩形，这反过来意味着我们使用了少量的矩形。

但是，这只是我想到的一个概念，还没有付诸实践。这似乎效率很低，所以我想知道是否有任何已知的快速算法来实现这一点？

4

4 回答 4

4

我真的一直在思考这个问题，所以我查看了已发表的研究。事实证明，如果您想要一个最佳解决方案，这是一个很难有效解决的问题（如果您想成为技术人员，则为 NP-Hard）。如果您不想相信我的话，请查看信息和控制中的论文“用矩形覆盖多边形的算法”。论文中有很多有趣的想法，作者给出了一种寻找最优覆盖的算法。显然它不会在多项式时间内运行，但对于您大小的问题实例来说它可能足够快。您甚至可能想先尝试一种更简单的耗尽技术，看看它是否适用于您感兴趣的问题。

这是我最初的建议，我将不再保证它是最佳的，尽管我还没有遇到反例：

从一个名为 R 的空矩形集合开始。对于数组中值为 1 的每个位置 (i,j)，找到包含 (i,j) 的 1s 中最宽的矩形 W，然后将 W 添加到矩形中包含所有 1 的最大高度 M。如果集合 R 不存在，则将 M 添加到集合 R。完成后，通过 R 并删除任何被 R 中其他矩形完全覆盖的矩形。

于 2009-11-25T18:28:38.143 回答
3

您是否考虑过将二维数组视为卡诺图？有一些算法（例如Quine-McClusky 算法）用于合并布尔真值表的单元格，这看起来像您正在尝试做的事情。

于 2009-11-20T17:03:03.093 回答
1

请注意，您描述的贪心算法并不总是最优的。考虑

01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX
01110       .XXX.
11111       XXXXX

如果你从最大的矩形开始，你会得到一个高的，然后是很多小边，产生 15 个矩形。另一方面，如果你只做小的水平矩形，你可以只用 14 个。

于 2009-11-20T16:56:23.560 回答
1

存在 O(N^2) 算法，可让您找到由 1 组成的最大矩形子矩阵。找到这个子矩阵并在它周围放置矩形。然后用零替换其中的那些，以避免将它们包含在后续的矩形中。再次应用该算法以找到下一个矩形。以此类推，直到没有人离开。

这种贪心算法当然不能保证最优解，最坏情况下复杂度为O(N^4)。

输入数据的最大大小是多少？

于 2009-11-20T17:03:55.083 回答