找到最大的子矩阵算法 [英] find largest submatrix algorithm

问题描述

予具有N * N的矩阵（N = 2〜10000），其可以范围从0到1000的数字。 我怎样才能找到最大的（矩形）子矩阵，由同一批？

I have an N*N matrix (N=2 to 10000) of numbers that may range from 0 to 1000. How can I find the largest (rectangular) submatrix that consists of the same number?

例如：

     1  2  3  4  5
    -- -- -- -- --
1 | 10  9  9  9 80
2 |  5  9  9  9 10
3 | 85 86 54 45 45
4 | 15 21  5  1  0
5 |  5  6 88 11 10

输出应的子矩阵的区域，其次是它的左上角元件的基于1的坐标。对于这个例子，这将是（6，2，1），因为有六个 9 取值位于第2列，第1行。

The output should be the area of the submatrix, followed by 1-based coordinates of its top left element. For the example, it would be (6, 2, 1) because there are six 9s situated at column 2, row 1.

推荐答案

这是一项正在进行的工作

我想过这个问题，我想我可能有一个 0（W * H）算法。

I thought about this problem and I think I may have a O(w*h) algorithm.

我们的想法是这样的：

• 任何（I，J）计算次数最多的细胞，在列的值相同Ĵ从启动（I，J）。存储这个值的高度[I] [J] 。
• 创建子矩阵的一个空向量（LIFO）
• 所有行：我
  • 所有列：J-
    • 在弹出的所有子矩阵，其高度＆GT;高度[I] [J] 。因为随着高度的子矩阵> 的高度[I] [J] 无法继续在该小区
    • 推按定义的子矩阵（I，J，高度[I] [J]。），其中Ĵ是在最远的坐​​标，我们可以适应高度的子矩阵：的高度[I] [J]
    • 更新当前的最大子矩阵
    • for any (i,j) compute the highest number of cells with the same value in the column j starting from (i,j). Store this values as heights[i][j].
    • create an empty vector of sub matrix (a lifo)
    • for all row: i
      • for all column: j
        • pop all sub matrix whose height > heights[i][j]. Because the submatrix with height > heights[i][j] cannot continue on this cell
        • push a submatrix defined by (i,j,heights[i][j]) where j is the farest coordinate where we can fit a submatrix of height: heights[i][j]
        • update the current max sub matrix

        最棘手的部分是在内部循环。我使用类似的东西来最大的子窗口的算法，以确保它是 O（1）平均每个细胞。

        The tricky part is in the inner loop. I use something similar to the max subwindow algorithm to ensure it is O(1) on average for each cell.

        我会努力制定一个证明，但这里同时是code。

        I will try to formulate a proof but in the meantime here is the code.

        #include <algorithm>
        #include <iterator>
        #include <iostream>
        #include <ostream>
        #include <vector>
        
        typedef std::vector<int>   row_t;
        typedef std::vector<row_t> matrix_t;
        
        std::size_t height(matrix_t const& M) { return M.size(); }
        std::size_t width (matrix_t const& M) { return M.size() ? M[0].size() : 0u; }
        
        std::ostream& operator<<(std::ostream& out, matrix_t const& M) {
          for(unsigned i=0; i<height(M); ++i) {
            std::copy(begin(M[i]), end(M[i]),
                  std::ostream_iterator<int>(out, ", "));
            out << std::endl;
          }
          return out;
        }
        
        struct sub_matrix_t {
          int i, j, h, w;
          sub_matrix_t(): i(0),j(0),h(0),w(1) {}
          sub_matrix_t(int i_,int j_,int h_,int w_):i(i_),j(j_),h(h_),w(w_) {}
          bool operator<(sub_matrix_t const& rhs) const { return (w*h)<(rhs.w*rhs.h); }
        };
        
        
        // Pop all sub_matrix from the vector keeping only those with an height
        // inferior to the passed height.
        // Compute the max sub matrix while removing sub matrix with height > h
        void pop_sub_m(std::vector<sub_matrix_t>& subs,
                   int i, int j, int h, sub_matrix_t& max_m) {
        
          sub_matrix_t sub_m(i, j, h, 1);
        
          while(subs.size() && subs.back().h >= h) {
            sub_m = subs.back();
            subs.pop_back();
            sub_m.w = j-sub_m.j;
            max_m = std::max(max_m, sub_m);
          }
        
          // Now sub_m.{i,j} is updated to the farest coordinates where there is a
          // submatrix with heights >= h
        
          // If we don't cut the current height (because we changed value) update
          // the current max submatrix
          if(h > 0) {
            sub_m.h = h;
            sub_m.w = j-sub_m.j+1;
            max_m = std::max(max_m, sub_m);
            subs.push_back(sub_m);
          }
        }
        
        void push_sub_m(std::vector<sub_matrix_t>& subs,
                int i, int j, int h, sub_matrix_t& max_m) {
          if(subs.empty() || subs.back().h < h)
            subs.emplace_back(i, j, h, 1);
        }
        
        void solve(matrix_t const& M, sub_matrix_t& max_m) {
          // Initialize answer suitable for an empty matrix
          max_m = sub_matrix_t();
          if(height(M) == 0 || width(M) == 0) return;
        
          // 1) Compute the heights of columns of the same values
          matrix_t heights(height(M), row_t(width(M), 1));
          for(unsigned i=height(M)-1; i>0; --i)
            for(unsigned j=0; j<width(M); ++j)
              if(M[i-1][j]==M[i][j])
            heights[i-1][j] = heights[i][j]+1;
        
          // 2) Run through all columns heights to compute local sub matrices
          std::vector<sub_matrix_t> subs;
          for(int i=height(M)-1; i>=0; --i) {
            push_sub_m(subs, i, 0, heights[i][0], max_m);
            for(unsigned j=1; j<width(M); ++j) {
              bool same_val  = (M[i][j]==M[i][j-1]);
              int pop_height = (same_val) ? heights[i][j] : 0;
              int pop_j      = (same_val) ? j             : j-1;
              pop_sub_m (subs, i, pop_j, pop_height,    max_m);
              push_sub_m(subs, i, j,     heights[i][j], max_m);
            }
            pop_sub_m(subs, i, width(M)-1, 0, max_m);
          }
        }
        
        matrix_t M1{
          {10,  9,  9,  9, 80},
          { 5,  9,  9,  9, 10},
          {85, 86, 54, 45, 45},
          {15, 21,  5,  1,  0},
          { 5,  6, 88, 11, 10},
        };
        
        matrix_t M2{
          {10, 19,  9, 29, 80},
          { 5,  9,  9,  9, 10},
          { 9,  9, 54, 45, 45},
          { 9,  9,  5,  1,  0},
          { 5,  6, 88, 11, 10},
        };
        
        
        int main() {
          sub_matrix_t answer;
        
          std::cout << M1 << std::endl;
          solve(M1, answer);
          std::cout << '(' << (answer.w*answer.h)
                << ',' << (answer.j+1) << ',' << (answer.i+1) << ')'
                << std::endl;
        
          answer = sub_matrix_t();
          std::cout << M2 << std::endl;
          solve(M2, answer);
          std::cout << '(' << (answer.w*answer.h)
                << ',' << (answer.j+1) << ',' << (answer.i+1) << ')'
                << std::endl;
        }
        

        这篇关于找到最大的子矩阵算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！