algorithm - 方阵中的最小矩形曲面 - 算法

Question

有人能指出我解决以下问题的正确方法吗:我有一个方阵 (N*N)，其中填充了 0 和 1 的值。我需要在矩阵中找到两个矩形，因此他们会检查以下条件:

1. 矩阵中1的每个元素，必须包含在至少一个矩形中；

2. 两个矩形的面积之和必须最小(允许其中一个矩形的面积为0)。

更具体的说什么是矩形:一个矩形由两个区间[a1, b1], [a2, b2]定义，包含所有矩阵单元格(i,j)使得a1≤i≤b1 , a2≤j≤b2。为了更清楚表面的含义:(b1-a1+1)·(b2-a2+1)。

你能帮我出点主意吗？非常感谢。

EDIT1:两个矩形可能重叠。

EDIT2:允许其中一个矩形的表面为 0

Answer 1

我原来的方法。这在最佳解决方案需要重叠矩形的情况下不起作用(例如，背景为 0 的 1 的“+”)。

1. Find the minimum bounding rectangle containing all the 1s.
2. Your first rectangle extends from the top-left of this bounding rectangle and your second bounding rectangle extends from the bottom-right of this bounding rectangle.
3. For each row R between the top and bottom of the bounding rectangle, create candidate rectangles extending from the top to R and from the bottom to R, both the width of the bounding rectangle.
4. Reduce both of these candidates so that they are minimum bounding rectangles of the 1s within them. These rectangle pairs all satisfy Point 1. Keep the minimum one over all R.
5. Repeat from Step 2 to cover every pair of corners in the overall bounding rectangle and keep the best solution overall.

经过多次失败的有效解决方案尝试(每次都在某些情况下失败)后，我认为能够找到最佳解决方案的唯一方法如下:

只需要考虑1的外接矩形。两个边界矩形不会位于该区域之外。假设边界矩形从行 (R1, C1) 到 (R2, C2)。

    For S1 in R1 to R2
        For S2 in S1 to R2
            For D1 in C1 to C2
                For D2 in D1 to C2
                    Reduce the rectangle (S1, C1)-(S2, C2) to be the minimum bounding rectangle of the 1s it contains
                    Reduce the rectangle (R1, D1)-(R2, D2) to be the minimum bounding rectangle of the 1s it contains that aren't already in the other rectangle. This is a candidate solution.

                    Reduce the rectangle (R1, D1)-(R2, D2) to be the minimum bounding rectangle of the 1s it contains.
                    Reduce the rectangle (S1, C1)-(S2, C2) to be the minimum bounding rectangle of the 1s it contains that aren't already in the other rectangle. This is another candidate solution.

选择您找到的最佳候选解决方案。

---

注意事项:

• 最好的解决方案不会有重叠的矩形，因为这样的解决方案总是可以通过减少其中一个矩形使其不再重叠来改进。因此，我们只需要在第 3 步中选择一个 R(而不是为每个矩形选择独立的最大行数)。
• 按行 (R) 还是按列 (C) 拆分并不重要，但没有必要同时进行。为了提高速度，您可以在边界矩形又短又粗时选择行，而在边界矩形又高又薄时选择列。
• 如果您找到一个候选解决方案，其中两个矩形都不包含任何零，那么它一定是最佳解决方案，您可以停止。