在矩阵中找到最大同行正方形的算法

Question

我有一个 100x100 大小的矩阵，需要找到最大的一组行和列来创建一个具有相同行的正方形。示例:

  A B C D E F               C D E 
a 0 1 2 3 4 5         a     2 3 4 
b 2 9 7 9 8 2                       
c 9 0 6 8 9 7   ==>                   
d 8 9 2 3 4 8         d     2 3 4    
e 7 2 2 3 4 5         e     2 3 4
f 0 3 6 8 7 2          

目前我正在使用这个算法:

candidates = [] // element type is {rows, cols}
foreach row
    foreach col
        candidates[] = {[row], [col]}
do
    retval = candidates.first
    foreach candidates as candidate
        foreach newRow > candidates.rows.max
            foreach newCol > candidates.cols.max
                // compare matrix cells in candidate to newRow and newCol
                if (newCandidateHasEqualRows)
                    newCandidates[] = {candidate.rows+newRow, candidate.cols+newCol}
    candidates = newCandidates
while candidates.count
return retval

有没有人遇到过类似的问题？有没有更好的算法来解决？

Answer 1

这是我提到的 NP 硬度降低，来自 biclique。给定一个二部图，创建一个矩阵，其中 A 部分的每个顶点都有一行，B 部分的每个顶点都有一列。对于存在的每条边，将 0 放入相应的矩阵条目中。为每个其他矩阵条目放置一个唯一的正整数。对于所有 s > 1，当且仅当存在大小为 s 的正方形(必然全为零)时，才存在 Ks,s 子图。

给定一组固定的行，很容易确定最佳的列集。你可以试试 a priori algorithm在行集上，其中一组行被认为是频繁当且仅当存在尽可能多的列与行一起形成一个有效的正方形。