在一个稀疏矩阵中找到最密集的n*n子矩阵

Question

我有一个边长为2*n的稀疏方阵。

例如：

1,0,0,1,0,1
0,1,1,1,0,1
1,0,0,0,1,1
0,0,1,1,0,0
1,1,1,0,0,0
0,0,0,1,1,0

我需要一种高效的方法来查找一个大小为n x n的子矩阵，其中1的数量最多。

我已经找到了各种方法来实现它，但没有一种比O(n^4)更快的方法。我还发现了更快的方法，但是不需要子矩阵必须是n x n。

编辑： 子矩阵必须是连续的。

- user2319925

Answer 1

根据您所述的O(n^4)时间复杂度算法，我假设子矩阵必须是连续的，否则问题是NP难的（比检测双团还要难）。对于O(n^2)时间复杂度算法，只需要进行O(n^2)预处理即可，使得可以进行“给定a、b、c、d，计算sum_{i=a}^bsum_{j=c}^dX[i,j]”形式的O(1)查询。

给定数组X[1..m,1..n]，按如下方式计算数组Y[0..m,0..n]。

initialize Y to the zero array
for i from 1 to m
    for j from 1 to n
       Y[i,j] = Y[i-1,j] + X[i,j]
    end
end
for i from 1 to m
    for j from 1 to n
       Y[i,j] = Y[i,j-1] + Y[i,j]
    end
end

现在，Y[c,d] = sum_{i=1}^c sum_{j=1}^d X[i,j]。要计算sum_{i=a}^b sum_{j=c}^d X[i,j]，可以使用容斥原理：Y[c,d] - Y[a-1,d] - Y[c,b-1] + Y[a-1,b-1]。

- David Eisenstat

---

这似乎不够。对于nxn的子矩阵，仍然有((2n)C(n))^2种选择。您已经描述了如何在O(1)时间内评估每个子矩阵的分数，给定O(n^2)的预处理，但仍然有很多选择要枚举。这种“积分图像”方法仅适用于矩阵空间排列（如图像）。但是在这里，“子矩阵”通常定义为由任意可能非连续的行和列的子集选定的元素。 - Timothy Shields

@TimothyShields 我假设子矩阵必须是连续的，因为提问者声称有一个O(n^4)算法，而非连续变体通过从双团约简是NP难问题。 - David Eisenstat

可能最好还是说明一下这个假设，因为提问者的O(n^4)说法有可能是错误的。 - Timothy Shields