dynamic-programming - 位图模式识别

Question

描述并分析一种算法，该算法可以找到在给定位图中出现多次的最大面积矩形图案。具体来说，给定一个二维数组 M[1 .. n, 1 .. n] 作为输入，您的算法应该输出 M 中最大重复矩形图案的面积。例如，给定左侧显示的位图在下图中，您的算法应返回整数 195，即 15 x 13 doggo 的面积。（虽然在本例中没有发生，但重复图案的两个副本可能会重叠。） 图片： 在此处输入图片描述

标签： dynamic-programming

Answer 1

使用术语矩形而不是子矩阵。

蛮力方法 O(n^8)
在矩阵中取两个不同的位置 A 和 B。然后考虑矩阵中以 A 为左上角的所有矩形。类似地考虑所有以 B 为左上角的矩形。假设我们有一个矩形，其左上角 A 的长度为l，宽度为b，然后取对应的矩形，左上角为 B ，长度l，呼吸b（假设这两个矩形都存在）。如果两个矩形的每一位都匹配，那么我们就有一个lb重复的面积模式，如果lb大于之前看到的最大面积，则更新最大面积。
对所有 A 和 B 对重复此过程。

时间复杂度：在不使分析复杂的情况下，让我们假设对于矩阵中的每个点P，对于所有以P为左上角的矩形，矩形的可能最大长度为n（但这不是真的，例如考虑最后一个点矩阵的行和最后一列）。让我们对矩形的最大可能呼吸做出类似的假设。
然后从乘积规则计算，有n^2个可能的矩形，点P为左上角。
这个估计还不错，因为根据这个，总共有 n^4 个矩形，因为矩形中有 n^2 个点，每个点有 n^2 个矩形。
实际答案是 ( (n+1) 选择 2 ) * ( (n+1) 选择 2 )，即 n^4 的顺序

所以总的来说，对于每一对，我们会比较 n^2 个矩形。和上面类似，让我们估计每个矩形中有n^2个点以便于计算。因此，对于一对点 A 和 B，我们将进行 O(n^4) 比较，因为对于每个矩形，我们需要检查它们的所有对应点。

总共有 (n^2 选择 2) 对点，其阶数为 n^4。所以我们的整体时间复杂度为 O(n^8)。

避免重复计算 O(n^6)
我们看到我们一次又一次地重复检查同一区域。例如，考虑两个左上角分别位于 A 和 B 的矩形，长度为l，宽度为b。同样，当我们在 A 和 B 处检查另一个具有左上角且长度为(l+1)和宽度为b的相应矩形时，我们再次检查长度为l和宽度b的矩形。

所以我们使用memoization来避免重复计算。
假设矩形的长度是水平测量的，宽度是垂直测量的。
考虑长度为l+1和宽度为b的矩形在 A 和 B 的左上角。现在我们需要比较矩形中对应点的所有值是否匹配。A_r、B_r 分别指向 A 和 B 的右侧。然后，如果矩形对于所有对应点具有相同的值，则长度为l、宽度为b且左上角为 A 和 B 的矩形必须重复。类似地，左上角位于 A_r 和 B_r 的长l宽b的矩形必须匹配。
考虑下图：

时间复杂度通过上述过程，比较两个矩形需要 O(1) 时间。因此，与上述情况相比，时间复杂度降低了 n^2 倍（这是在早期情况下比较矩形所需的时间）。所以在这种情况下 O(n^6) 时间。

让我们将 (P, m, n) 表示为具有左上角 P、长 m 和宽 m 的矩形。

去除不必要的计算 O(n^5)
在上述方法中，即使我们知道如果矩形 (A, l, b) 和 (B, l, b) 不匹配，我们再次比较矩形 (A, l+1 , b) 和 (B, l+1, B)。
所以假设现在我们有左上角 A 和 B 长度为l的矩形，那么矩形的最大可能宽度是多少？
如果每个矩形顶行的所有对应元素都不匹配，则答案为 0。但如果所有对应行都匹配，则答案为 1 + (长度为l但左上角低于 A的矩形的最大宽度和 B)。

与上述方法类似，此计算将花费 O(1) 时间，因为我们需要 (A, B, l-1) 的宽度和以下长度为 l 的矩形的宽度。

请参阅此答案Largest Square Block以获得更清晰的信息。

时间复杂度对于矩阵中的每一对点，我们必须存储最大值。长度 1、2、...n 的宽度。并且有 n^4 个这样的对。我们可以检查在 O(1) 时间内获得每个值。所以整体时间复杂度是O(n^5)。并找到最大值。每对矩形的每个长度的面积在这里很明显。

进一步优化 O(n^4)
假设您有两个位图副本。一个被粘在地上，另一个可以在被粘的上面移动。让我们将固定的一张称为基础，另一张称为移动位图。
现在，移动位图的左上角可以位于基址的 (n^2 - 1) 个点之一上，但移动位图位于基址顶部的情况除外。现在在每种情况下，都会有一些点被遗漏，即对于基本位图上的一些点，不会有在其顶部移动一个点，反之亦然。假设移动位图的左上角需要在其下方有一个基本位图元素。

现在以这些 (n^2 - 1) 配置的一个实例为例。对于移动位图上所有在其下方有一个基本位图点的点，让我们构造一个新矩阵，如果两个位图的顶部和底部元素相同，则它包含“Y”，否则它包含“N” . 请记住，矩阵的大小与移动位图上没有基本位图元素的元素相同。

然后，基本位图和移动位图的那部分重复图案的最大区域将是包含所有 Y 的最大实心块区域，这可以在 O(n^2) 时间内完成。
我们要求的答案是所有这些 (n^2 - 1) 配置中的最大答案。

请参阅包含所有 Y 的最大矩形以获得进一步的清晰度

时间复杂度对于每种配置，构建“Y”和“N”的新矩阵将花费 O(n^2) 时间，最大面积计算也需要 O(n^2) 时间。并且有 (n^2- 1) 个这样的配置，所以总的 O(n^4) 时间。

注意 Jeff Erickson 表示可以在 O(n^3 polylog n) 时间内计算出答案。我不知道该怎么做。如果有人发布这样的算法会很好。