algorithm - 使用贪心方法，给定一个 m × n 布尔矩阵 B，找到其元素全为零的最大平方子矩阵

Question

任何人都知道使用贪婪的方法请帮助我解决这个问题。我已经通过动态方法完成了这个。但我主要关心的是使用贪婪方法。而且我们还必须找到 0 的最大平方子矩阵。 https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/ 这是使用动态方法并查找具有 1 的元素的示例。注意：使用贪心

标签： algorithmgreedy

Answer 1

贪婪方法是您做出局部最优选择的地方，相信它会导致最优解。所以基本上我们首先在 mXn 矩阵的四个边距之一中搜索 0，即在第一行、最后一行、第一列或最后一列。一旦找到 0，我们就开始寻找可能的最大正方形。

例子-

0 0 1 1 0 0

1 0 0 0 0 0

1 1 1 0 0 0

1 1 1 0 0 0

1 0 0 0 0 0

在上面的例子中，第一个元素是 0，所以检查 5X5 矩阵的存在，它失败了，因为第三个元素是 1。现在有几种情况-

1] 如果您离开进一步评估的第一行，您仍然可以瞄准大小为 4X4 的矩阵。

2] 如果您离开第三列并仅考虑前两列，则瞄准 2X2 矩阵。

3] 如果您离开第三列并仅考虑最后三列，则瞄准 3X3 矩阵。

4] 我们不会考虑同时删除行和列的选项，因为它不会比前三个选项更好。

考虑到贪婪，我们会选择第一种情况并重复该过程。