1と0が等しくない最大サブマトリクス

Question

0と1を含むサイズmxnの行列が与えられているとします。私はそれに1と0の等しい数を持つ最大の部分行列を見つける必要があります。ブルートフォースのアプローチはO(m^2*n^2)となるでしょうか？
私は動的プログラミングを適用しようとしましたが、最適な部分構造が見つかりませんでした。

私はこの問題の類似した一次元バージョンは、ここで議論されたと信じて：
Space-efficient algorithm for finding the largest balanced subarray?
いくつかの余分なスペースを使用してO(n)ソリューションを持っています。

Answer 1

このアルゴリズムでは、連続する行と列、および可能な限り大きな高さと幅の積でサブ行列を検索することを前提としています。以下、前処理と

スタート：行（i、j）の各対について今

A = substitute_zero_with_minus_one(InputMatrix) 
B = prefix_sum_for_each_column(A) 
C = prefix_sum_for_each_row(B) 

はfolowingない：

for each column k: 
    d = C[k, j] - C[k, i] 
    if h[d] not empty: 
    if (k - h[d]) * (j - i) is greater than best result: 
     update best result 
    else: 
    h[d] = k 

時間計算量はO（N * M）、余分なスペースはO（N * M）です。

Answer 2

私はm <と仮定し、O（M * M * N）アルゴリズムを持つことができます。 は、我々はすべて0 -1で置き換えるならば、私たちはその合計0

1. ある各行のセグメント（i、j）の合計を取得する最大のsubmaxtrixを見つけ、我々は彼らにC1、C2を定義し、 c3 ....、cn、私たちは アルゴリズムでO（n）アルゴリズムを実行することができます。
2. 手順1をM * M回実行して、合計が0である最大サブマスク行列を取得する必要があります。したがって、複雑さはO（M * M * N）です。

Answer 3

オリジナル行列の連続した行/列のみを使用して部分配列が形成されたと仮定します（つまり最初の最後の行を削除します）。

このように、元の行列は次元M×N個である場合、行列は

Mat = {origin(row,col), rowCount, columnCount} 

として表すことができ、次いで

rowCount = M - row 
columnCount = N - col 
Mat = {origin(row,col), M - row, N - col}. 

可変rowとcolそれぞれMと可能Nを有します値は、 を意味し、O(MxN)のような行列です。キュー

試験からアルゴリズム

1. ポップマトリックス(m, n)の

   アイデア。成功した場合は、出力行列

2. すべての行列を構築する(m, n-1)と(m-1, n)そして待ち行列に入れる
3. 1に戻る。あなたは寸法を小さくする場合にのみ、4つの可能な行列（列を除去することにより、行、2を除去することにより、2）
4. あなたはどちらかの削除によりサブ行列を構成
   • があります。今の2点があります

最初と最後の行\列。削除した行\列のカウントを削除する必要があります。これには、O(n)またはO(m)時間がかかります。これは動的プログラミングのステップです。複雑さを意味

は、私は、検索アルゴリズムの最適化を実証する小さなアプリケーションを作成しO(max(M,N)MN)

Answer 4

です。これがあなたが探しているものなら教えてください。

注：

1. プログラムは読みやすさのために正方行列
2. を作成し、私はデータで動作するようにコレクションを使用しています。私は処理に過負荷があると信じていますが、私はその原則を指摘しようとしています。

ここにある：

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 

class Program 
{ 
    class Matrix 
    { 
     public int[][] JaggedInteger2DMatrix { get; set; } 

     public List<MatrixCell> Cells { get; set; } 
     public List<MatrixLine> Lines { get; set; } 

     public int Width { get; set; } 
     public int Height { get; set; } 

     public Matrix(int size, int seed) 
     { 
      var r = new Random(seed); 
      int[][] jaggedInteger2DMatrix = new int[size][]; 
      for (int i = 0; i < size; i++) 
      { 
       jaggedInteger2DMatrix[i] = new int[size]; 
       for (int j = 0; j < size; j++) 
       { 
        jaggedInteger2DMatrix[i][j] = r.Next(2); 
        //Console.Write(jaggedInteger2DMatrix[i][j]+" "); 
       } 
       //Console.Write("\r\n"); 
      } 
      InitializeMatrix(jaggedInteger2DMatrix); 
     } 

     public Matrix(int[][] jaggedInteger2DMatrix) 
     { 
      InitializeMatrix(jaggedInteger2DMatrix); 
     } 

     private void InitializeMatrix(int[][] jaggedInteger2DMatrix) 
     { 
      JaggedInteger2DMatrix = jaggedInteger2DMatrix; 
      Height = jaggedInteger2DMatrix.GetLength(0); 
      Width = jaggedInteger2DMatrix[0].GetLength(0); 
      Cells = new List<MatrixCell>(); 
      Lines = new List<MatrixLine>(); 
      int horizontalLineCounter = 0; 
      MatrixCell matrixCell = null; 
      foreach (var horizontalLine in jaggedInteger2DMatrix) 
      { 
       int verticalLineCounter = 0; 
       foreach (var cell in horizontalLine) 
       { 
        matrixCell = new MatrixCell() 
        { 
         HorizontalLineIndex = horizontalLineCounter, 
         Value = cell, 
         VerticalLineIndex = verticalLineCounter 
        }; 
        Cells.Add(matrixCell); 

        if (Lines.Where(line => line.LineType == Line.Vertical && line.LineIndex == verticalLineCounter).Count() == 0) 
        { 
         var line = new MatrixLine() 
         { 
          LineType = Line.Vertical, 
          LineIndex = verticalLineCounter 
         }; 
         Lines.Add(line); 
        } 

        Lines.Where(line => line.LineType == Line.Vertical && line.LineIndex == verticalLineCounter).FirstOrDefault().Cells.Add(matrixCell); 

        if (Lines.Where(line => line.LineType == Line.Horizontal && line.LineIndex == horizontalLineCounter).Count() == 0) 
        { 
         var line = new MatrixLine() 
         { 
          LineType = Line.Horizontal, 
          LineIndex = horizontalLineCounter 
         }; 
         Lines.Add(line); 
        } 

        Lines.Where(line => line.LineType == Line.Horizontal && line.LineIndex == horizontalLineCounter).FirstOrDefault().Cells.Add(matrixCell); 

        verticalLineCounter++; 
       } 
       horizontalLineCounter++; 
      } 
     } 

    } 

    class MatrixCell 
    { 
     public int Value { get; set; } 
     public int VerticalLineIndex { get; set; } 
     public int HorizontalLineIndex { get; set; } 
    } 

    class MatrixLine 
    { 
     public Line LineType { get; set; } 
     public int LineIndex { get; set; } 
     public List<MatrixCell> Cells { get; set; } 
     public MatrixLine() 
     { 
      Cells = new List<MatrixCell>(); 
     } 
    } 

    enum Line 
    { 
     Horizontal, 
     Vertical 
    } 

    private static void Search(Matrix matrix, bool optimizeCellCount, out IEnumerable<MatrixCell> optimizedSelection, out int iterations) 
    { 
     optimizedSelection = null; 

     var count = 0; 
     iterations = 0; 
     for (int i = 0; i < matrix.Width; i++) 
     { 
      for (int j = 1; j <= matrix.Width; j++) 
      { 
       var selectedVerticalLines = matrix.Lines.Where(line => line.LineType == Line.Vertical).Skip(i).Take(j); 
       for (int k = 0; k < matrix.Height; k++) 
       { 
        for (int l = 1; l <= matrix.Height; l++) 
        { 
         /** 
         * Here's where the search is optimized 
         ********************************************************************************************** 
         */ 
         if (optimizeCellCount) 
         { 
          //if the submatrix cell count is smaller than the current count, break the iteration 
          if (count > Math.Min(Math.Abs(matrix.Height - k), l) * Math.Min(Math.Abs(matrix.Height - i), j)) 
          { 
           continue; 
          } 
         } 
         /* 
         ********************************************************************************************** 
         */ 
         iterations++; 

         var selectedHorizontalLines = matrix.Lines.Where(line => line.LineType == Line.Horizontal).Skip(k).Take(l); 

         var horizontalCells = selectedHorizontalLines.Aggregate<MatrixLine, List<MatrixCell>>(new List<MatrixCell>(), (a, b) => 
         { 
          a.AddRange(b.Cells); 
          return a; 
         }); 
         var verticalCells = selectedVerticalLines.Aggregate<MatrixLine, List<MatrixCell>>(new List<MatrixCell>(), (a, b) => 
         { 
          a.AddRange(b.Cells); 
          return a; 
         }); 

         var cells = horizontalCells.Intersect(verticalCells); 
         if (cells.Count() > count) 
         { 
          var sum = cells.Sum(t => t.Value); 
          var cellsCount = cells.Count(); 
          if (sum != 0) 
          { 
           if (cellsCount/(double)sum == 2) 
           { 
            //match 
            optimizedSelection = cells; 
            count = cellsCount; 

           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 

    private static float GetLineCost(int width, int startPosition, int length) 
    { 
     float cost = 0; 
     for (int i = startPosition; i < length; i++) 
     { 
      cost += Math.Min(Math.Abs(width - i), i + 1); 
     } 
     return cost; 
    } 

    static void Main(string[] args) 
    { 
     Matrix matrix = new Matrix(20, 1); 

     bool optimizeCellCount = true; 

     IEnumerable<MatrixCell> optimizedSelection; 
     int iterations; 

     var watch = new System.Diagnostics.Stopwatch(); 

     //optimized search 
     watch.Start(); 
     Search(matrix, optimizeCellCount, out optimizedSelection, out iterations); 
     watch.Stop(); 
     Console.WriteLine("Full Optimized Search"); 
     Console.WriteLine("position: [{0},{1}],[{2},{3}] size : {4} search time : {5} iterations: {6}", 
      optimizedSelection.Min(cell => cell.VerticalLineIndex), 
      optimizedSelection.Min(cell => cell.HorizontalLineIndex), 
      optimizedSelection.Max(cell => cell.VerticalLineIndex), 
      optimizedSelection.Max(cell => cell.HorizontalLineIndex), 
      optimizedSelection.Count(), 
      watch.Elapsed, 
      iterations 
      ); 
     watch.Reset(); 

     //no optimization 
     watch.Start(); 
     Search(matrix, !optimizeCellCount, out optimizedSelection, out iterations); 
     watch.Stop(); 
     Console.WriteLine("Non-Optimized Search"); 
     Console.WriteLine("position: [{0},{1}],[{2},{3}] size : {4} search time : {5} iterations: {6}", 
      optimizedSelection.Min(cell => cell.VerticalLineIndex), 
      optimizedSelection.Min(cell => cell.HorizontalLineIndex), 
      optimizedSelection.Max(cell => cell.VerticalLineIndex), 
      optimizedSelection.Max(cell => cell.HorizontalLineIndex), 
      optimizedSelection.Count(), 
      watch.Elapsed, 
      iterations 
      ); 
     watch.Reset(); 

     //Console Output: 
     /*************************************************************************************** 
     * Full Optimized Search 
     * position: [9,1],[18,19] size : 190 search time : 00:00:02.3963657 iterations: 19108 
     * Non-Optimized Search 
     * position: [9,1],[18,19] size : 190 search time : 00:00:05.8385388 iterations: 160000 
     ****************************************************************************************/ 

    } 
}