algorithm - 动态规划 : finding largest triangle

Question

我需要使用动态规划在零和一的矩阵中找到最大的三角形。所以如果这是我的矩阵:

 1 0 0 1 1
 0 1 1 1 1
 0 1 1 1 0
 1 1 1 1 1
 1 1 0 0 1

然后有两个最大的三角形，其右角位于 [2,2] 和 [4,4]。我只需要寻找直角等腰三角形(具有 90°、45°、45° 的角度)，而且我也只需要查看一个方向，因为所有其他方向都是对称的。所以基本上我需要一个函数，它接受矩阵并返回一个三角形，三角形是一个对象。我不需要完整的代码伪代码也可以。

首先我想到在这里使用平方算法:Dynamic programming - Largest square block ，当你找到了最大的正方形，那么最大的三角形一定在里面。但我可以很容易地找到这不起作用的反例。之后，我尝试查看上面的单元格并使用动态编程对其进行计数，但我不确定下一步该怎么做......所以我的计数看起来像上面的矩阵:

1 0 0 1 1
0 1 1 2 2
0 2 2 3 0
1 3 3 4 1
2 4 0 0 2

我认为必须以某种方式使用它。

更新:

我想我现在已经很接近了，当你遍历矩阵 n*m 并使 count[i][j] = 1+ min(count[i-1][j], count[i][j -1]), 所以看看左边和上面的单元格。我们得到这个:

1 0 0 1 1
0 1 1 2 2
0 1 2 3 0
1 2 3 4 1
1 2 0 0 1

这对我来说看起来很不错，你可以看到 [4,4] 解决方案的右角在哪里。谁能想到任何反例？我只需要返回一个解决方案，所以返回这个解决方案就可以了。

更新 2:我找到了一个反例，设位置[4,4]为0，我们得到如下矩阵:

 1 0 0 1 1
 0 1 1 1 1
 0 1 1 1 0
 1 1 1 0 1
 1 1 0 0 1

遍历矩阵后计数将如下所示:

1 0 0 1 1
0 1 1 2 2
0 1 2 3 0
1 2 3 0 1
1 2 0 0 1

现在它将返回右角为 [3,4] 的三角形(第三行第四列)，这是不正确的，它应该找到 [2,2]。所以我想也许只是从左上角(我们到目前为止所做的)和右下角开始，然后从中取最大值。因此，右下角的计数将如下所示(查看下方和右侧的单元格):

1 0 0 2 1
0 4 3 2 1
0 3 2 1 0
2 2 1 1 1
1 1 0 0 1

现在我们确实找到了 [2,2] 的解。所以我认为使用这些方法会给我解决方案，谁能想到更好的解决方案或反例？

更新 3:kraskevich 让我意识到我们必须使用这个算法四次。从左上角，右上角，左下角，右下角，然后取最大值，因为这样你就已经取了所有的可能性。任何人都有更好的方法来做到这一点？那么这个算法正确吗？ (所以只是四次相同的算法，只是矩阵中的另一个起点)

对于那些不真正了解我在做什么的人(我可能会说得有点快)再看看这个:Dynamic programming - Largest square block该方法非常相似，并且在那里做了很好的解释。

Answer 1

是的，你的想法几乎是正确的。让我们将其形式化。

声明:

f(i, j)是在 (i, j) 处具有右下角的最大三角形的大小位置并且计算正确。

证明:

让我们使用归纳法。

基本情况:对于第一行和/或第一列中的所有单元格，三角形的大小为 1 或 0(取决于此单元格中的值)。

归纳步骤:

让我们假设 f(i - 1, j)和 f(i, j - 1)已被正确计算。

1. f(i - 1, j) >= f(i, j) - 1和 f(i, j - 1) >= f(i, j) - 1 .这是因为三角形的任何子三角形都带有1 s 是 1 的三角形秒。这意味着 f(i, j) <= f(i - 1, j) + 1和 f(i, j) <= f(i, j - 1) + 1 ，或者，换句话说，f(i, j) <= min(f(i - 1, j) + 1, f(i, j - 1) + 1) = min(f(i - 1, j), f(i, j - 1)) + 1 .因此，f(i, j) <= min(f(i - 1, j), f(i, j - 1)) + 1成立。

2. 我们假设 min(f(i - 1, j), f(i, j - 1)) = k .然后是大小为k的三角形在(i - 1, j)单元格和另一个大小为 k 的三角形在(i, j - 1)细胞。连同(i, j)单元格，这两个三角形组成一个大小为k + 1的三角形.因此，f(i, j) >= min(f(i - 1, j), f(i, j - 1)) + 1 .

我刚刚展示了 f(i, j) >= min(f(i - 1, j), f(i, j - 1)) + 1和 f(i, j) <= min(f(i - 1, j), f(i, j - 1)) + 1 .这意味着 f(i, j) = min(f(i - 1, j), f(i, j - 1)) + 1 .因此 f(i, j)也被正确计算。

请注意，我们只考虑了直角位于右下角的三角形。为了考虑所有可能的三角形，我们可以简单地对给定矩阵的所有 4 种可能的旋转运行该算法。

让我们证明在 4 个方向上运行这个算法是足够的:

矩阵中任意直角等腰三角形的直角只有四种可能的位置:左下角、右下角、左上角和右上角。沿固定方向运行此算法会找到该方向的最大三角形(我已经在上面证明了)。因此，在所有可能的方向上运行该算法足以找到矩阵中的最大三角形。

这个算法在时间复杂度方面是最优的，因为它有一个 O(n * m)时间复杂度，仅仅读取输入就已经需要 O(n * m)时间(在一般情况下，如果不查看矩阵的所有元素，我们将无法找到答案)。