算法来寻找在一个二维数组矩形覆盖某些元素的最小数目 [英] Algorithm to find the minimum number of rectangles covering certain elements in a 2d array

问题描述

简体，我必须解决以下问题：

Simplified, I have to solve the following problem:

您有一个2维数组填充有0和1。发现它们涵盖全1的矩形这样的最小数目。矩形不应当重叠。

You have a 2-dimensional array filled with 0s and 1s. Find the minimum number of rectangles such that they cover all 1s. Rectangles should not overlap.

函数签名可能是这样的： 名单，其中，矩形＆GT; FindCoveringRectangles（布尔[，]数组）

The function signature might look like: List<Rectangle> FindCoveringRectangles(bool[,] array)

我已经有一个解决方案，那就是足够好，但并不一定是矩形的最低数量。我想知道是否有一些可应用于解决这个问题众所周知的，并且有效的算法

I already have a solution that is "good enough" but doesn't always find the minimum number of rectangles. I'd like to know if there is some well known and efficient algorithm that can be applied to solve this problem?

例如：

的输入数组：

..........
.1.....11.
.......11.
...111....
...111....
...111....
....1111..
....1111..
......11..
..........

（0由点的可读性代替）

(0s replaced by dots for readability)

可能导致以下的矩形

(2,2,2,2),
(2,8,3,9),
(4,4,6,6),
(7,5,8,8),
(9,7,9,8)

（上，左，下，右），1系

(top, left, bottom, right), 1-based

可以有一个以上的溶液，但一个是足够

There can be more than one solution, but one is enough.

推荐答案

这是一种匹配的问题，这可以很容易地显示NP难。然而，接缝有一个非常快速的解决方案。

This is a matching problem of a kind, that could easily have shown NP-hard. However it seams there is a very fast solution.

使用BFS洪水填充你可以找到每个连接的组件， O（N）。因此wlog我们可以假设，我们只需要填写一个连接的区域。

Using a bfs flood-fill you can find each connected component, O(n). Hence wlog we can assume that we just have to fill one connected area.

如果该区域没有在它的孔，你可以使用的本文。

If the area doesn't have holes in it, you can use the algorithm described in this paper.

这是 O（N日志日志N）算法为最小矩形分割的简单直线多边形。为任何简单直线多边形P，顶点边缘可见对是一个顶点且可由一个水平或垂直线段完全位于内部P.结果表明，如果顶点边缘可见对被发现被连接的边缘，最大匹配和最大独立集从一个简单的直线多边形的弦得到的二分图的可以在线性时间内找到了不构建二分图。使用这种算法，凸多边形直线和垂直方向上的最小划分问题（水平）凸多边形直线，可以为O解决（n）的时间

An O(n log log n) algorithm is proposed for minimally rectangular partitioning a simple rectilinear polygon. For any simple rectilinear polygon P, a vertex-edge visible pair is a vertex and an edge that can be connected by a horizontal or vertical line segment that lies entirely inside P. It is shown that, if the vertex-edge visible pairs are found, the maximum matching and the maximum independent set of the bipartite graph derived from the chords of a simple rectilinear polygon can be found in linear time without constructing the bipartite graph. Using this algorithm, the minimum partition problem for convex rectilinear polygons and vertically (horizontally) convex rectilinear polygons can be solved in O(n) time

有的称为还覆盖有孔的区域的情况下的论文。这些运行在为O（n ^（3/2）LOGN）虽然，但他们仍然缝pretty的好。

Some of the papers referred to also cover the case of an area with holes. These run in O(n^(3/2)logn) though, but they still seam pretty good.

另外，你可以做的是解决问题的无孔，解决问题的每一个孔，然后减去一件事。这可能不是给出一个最佳的解决方案，虽然，但会继续运行。

Alternatively, one thing you might do is solving the problem without holes, solving the problem for each hole, and then subtract. This might not give an optimal solution though, but would keep the runtime.

您也可以尝试，分裂在其不同的拓扑份的形状，但在孔的数量，将有可能成倍运行

You could also try and split the shape in its different topological parts, but that would likely run exponentially in the number of holes.

第三，你可以尝试去适应该算法的更一般的情况，但也可能是困难的。

Thirdly you could try to adapt the proposed algorithm for the more general case, but it might be hard.

这篇关于算法来寻找在一个二维数组矩形覆盖某些元素的最小数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！