0

我有一个 nxn 对称二进制矩阵，我想找到最大的矩形（区域），左上角和右下角为 0，右上角和左下角为 1。如果我只是用循环来做，检查从最大到最小的所有矩形，n=100 需要“天”。有没有人有想法有效地做到这一点？

非常感谢 ！

4

2 回答 2

0

谢谢你的回答。我使用的矩阵是随机 Erdos-Renyi 图的邻接矩阵。但是可以使用任何随机对称二进制矩阵来测试它。到目前为止，我使用 4 个嵌套循环：

switch<-function(Mat)
{
n=nrow(Mat) 
for (i in 1:(n-1)) { 
    for(j in seq(n,i+1,by=-1)) {
        for(k in 1:(n-1)) { 
            if ((k==i)||(k==j) || (Mat[i,k]==1)||(Mat[j,k]==0)) next 
            for(l in seq(n,k+1,by=-1)) { 
                if ((l==i)||(l==j)|| (Mat[i,l]==0)||(Mat[j,l]==1)) next 
                return(i,j,k,l)
            }
        }
    }
}
于 2022-02-23T16:56:07.960 回答
0

这是您现在可以尝试的一种方法。它不需要对称性，并且将所有非零元素视为效率。

它循环遍历那些，假设有比零少的。（在相反的情况下，您可能希望在零比一少的情况下循环零。）

这种方法可能不是最优的，因为即使早期识别出最大的盒子，它也会遍历所有的盒子。在这种情况下，您可以设计一个巧妙的停止条件来使循环短路。但它仍然很快n = 100，在我的机器上只需要不到半秒的时间，即使 1 和 0 以大致相等的比例出现（最坏的情况）：

f <- function(X) {
    if (!is.logical(X)) {
        storage.mode(X) <- "logical"
    }
    J <- which(X, arr.ind = TRUE, useNames = FALSE)
    i <- J[, 1L]
    j <- J[, 2L]
    nmax <- 0L
    res <- NULL
    for (k in seq_along(i)) {
        i0 <- i[k]
        j0 <- j[k]
        ok <- i < i0 & j > j0
        if (any(ok)) {
            i1 <- i[ok]
            j1 <- j[ok]
            ok <- !(X[i0, j1] | X[i1, j0])
            if (any(ok)) {
                i1 <- i1[ok]
                j1 <- j1[ok]
                n <- (i0 - i1 + 1L) * (j1 - j0 + 1L)
                w <- which.max(n)
                if (n[w] > nmax) {
                    nmax <- n[w]
                    res <- c(i0 = i0, j0 = j0, i1 = i1[w], j1 = j1[w])
                }
            }
        }
    }
    res
}

mkX <- function(n) {
    X <- matrix(sample(0:1, n * n, TRUE), n, n)
    X[upper.tri(X)] <- t(X)[upper.tri(X)]
    X
}

set.seed(1L)
X <- mkX(6L)
X
##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]    0    1    0    0    1    0
## [2,]    1    0    1    1    0    0
## [3,]    0    1    0    1    1    1
## [4,]    0    1    1    0    0    0
## [5,]    1    0    1    0    0    1
## [6,]    0    0    1    0    1    0

f(X)
## i0 j0 i1 j1 
##  5  1  1  5 

Y <- mkX(100L)
microbenchmark::microbenchmark(f(Y))
## Unit: milliseconds
##  expr     min       lq     mean   median       uq      max neval
##  f(Y) 310.139 318.3363 327.8116 321.4109 326.5088 391.9081   100
于 2022-02-23T18:04:00.510 回答