最大的矩形设置封面

2018-06-22 12:53:53

我有一个二进制矩阵，我试图找到所有矩阵中相邻元素可以形成的最大矩形。我指的是最大的矩形，所有矩形都是唯一的，而不是任何其他矩形的子集。例如，以下矩阵包含六个这样的矩形。

这与设置封面问题有关，尽管在这里我对最大数量的矩形感兴趣，而不是最小数量。我试过的一种方法是找到所有矩形，不管大小，然后比较矩形，如果它们是另一个矩形的子集，则将它们移除。这不是一个最佳方法。看起来这个套封面问题的情况应该不会太难。

我看了一下，没有发现类似于这个问题的东西。这篇论文有一些很好的想法，但仍然非常广泛。这个特殊问题有另一个名字吗？是否有任何现有算法用于在集合覆盖问题中查找所有可能的矩形？

在做了更多的工作后，我意识到这与设置封面问题没有关系。它实际上是“找到在二进制矩阵问题中没有包含在任何其他矩形内的唯一矩形”。

我想出了一些运作良好的东西，但我不知道它的复杂性。

基本上，水平和垂直扫过矩阵。在每种情况下，查找可以与下一行形成矩形的1的连续组。这会产生许多矩形，其中一些矩形是其他矩形的重复或子矩形。这些矩形被缩减为一个唯一的集合，其中没有矩形是另一个矩形的子矩形。那么你有所有的矩形。

以下是与原始帖子中图片相关的图表：

链接地址: http://www.djcxy.com/p/63239.html