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

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，存在 K_s,s 子图当且仅当存在大小为 s 的正方形（必然全为零）时。

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

Answer 2

我已经实现了 branch and bound solver for this problem in C++ at http://pastebin.com/J1ipWs5b。令我惊讶的是，它实际上可以相当快地解决随机生成的大小高达 100x100 的谜题：在一个问题中，每个矩阵单元从 0-9 中随机选择，在我的旧笔记本电脑上大约 750 毫秒内找到了最佳 4x4 解决方案。随着单元格条目的范围减少到仅 0-1，求解时间变得非常长——但仍然是 157 秒（对于我尝试过的一个问题，它有一个 8x8 最优解），这并不可怕。好像对最优解的大小很敏感

在任何时间点，我们都有一个部分解决方案，由一组明确包含的行和一组明确排除的行组成。（剩余行的收录状态待定。）首先，我们选择剩余行到"try"。我们尝试包括该行；然后（如有必要；见下文）我们尝试排除它。 "Trying"这里的意思是递归求解相应的子问题。我们记录在解决方案中明确包含的所有行中相同的列集。随着行被添加到部分解决方案中，这组列只能缩小。

当我们确定无法将当前的部分解决方案发展成比我们已经找到的某个完整解决方案更好（即更大）的完整解决方案时，除了标准 B&B 修剪搜索的想法之外还有一些改进:

支配规则。如果有任何行可以添加到当前的部分解决方案而根本不收缩相同列的集合，那么我们可以安全地立即添加它们，我们永远不必考虑 not 添加他们。这可能会节省大量分支，尤其是在输入中有许多相似行的情况下。
我们可以任意重新排序剩余的（未明确包含或明确排除）行。因此，特别是，我们总是可以选择下一行来考虑将最多缩小相同列集的行：这种（可能违反直觉的）策略具有消除错误组合的效果搜索树顶部附近的行，这大大加快了搜索速度。它也恰好补充了上面的优势规则，因为它意味着如果有两行 X 和 Y，使得 X 保留 Y 保留的相同列的严格子集，那么 X 将首先添加到解决方案中，这在turn的意思是只要包含X，Y就会被支配规则强行加入，不需要考虑包含X排除Y的可能性。

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

Algorithm to find largest identical-row square in matrix

algorithm

math

matrix

graph-algorithm