Największa podmatryca z równymi nr 1 i 0

Question

Podana jest macierz rozmiaru mxn zawierająca tylko cyfry 0 i 1. Muszę znaleźć największą pod-macierz, która ma taką samą liczbę 1 i 0 w niej. Metoda brutalnej siły będzie O(m^2*n^2) Czy możemy zrobić coś lepszego niż to?
Próbowałem zastosować dynamiczne programowanie, ale nie mogłem znaleźć optymalnej podkonstrukcji.

wierzę podobna wersja jednowymiarowa ten problem został omówiony tu:
Space-efficient algorithm for finding the largest balanced subarray?
który ma rozwiązanie O(n) używając trochę więcej przestrzeni.

Answer 1

Algorytm ten zakłada, że ​​przeszukujemy pod-macierz z sąsiednimi wierszami i kolumnami oraz z największym możliwym produktem wysokości i szerokości.

uruchamianiu z obróbki wstępnej:

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

Obecnie dla każdej pary rzędów (i, j) czy w następujące: złożoność

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 

czas O (N * M), dodatkowa przestrzeń to O (N * M).

Answer 2

Przyjmujemy m < n, i możemy mieć algorytm O (M * M * N). A jeśli wymienimy wszystkie 0 przez -1, po prostu znaleźć największą submaxtrix którego suma wynosi 0.

1. Get sumę segmentów (i, j) w każdym wierszu, możemy je zdefiniować C1, C2, c3 ...., cn, możemy uruchomić na nim algorytm O (n) według przywołanego algorytmu .
2. Powinniśmy wykonać krok 1 M * M razy, aby uzyskać największą submaxtrix, której suma wynosi 0, więc złożoność wynosi O (M * M * N).

Answer 3

Zakładam, że podmateria jest tworzona przy użyciu tylko sąsiadujących wierszy \ kolumn oryginalnej matrycy (przez usunięcie pierwszego \ ostatniego wiersza lub kolumn).

ten sposób, matryca może być reprezentowane

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

Jeśli oryginalna matryca ma wymiar M x N, to

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

Zmienna row i col jest odpowiednio M i N możliwy wartości, co oznacza jest takich macierzy.

Idea algorytmu

1. matrycy pop (m, n) z kolejki
2. Test. Jeśli powodzenie, macierz wyjściowa
3. Skonstruuj wszystkie macierze (m, n-1) i (m-1, n) i wstaw kolejkę
4. wróć do 1.

Teraz istnieją dwa punkty:

• Kiedy można zmniejszyć wymiary istnieją tylko 4 możliwych matryce (2 usuwając wiersze, 2 kolumnami usuwanie)
• skonstruować macierz sub by usunąć zarówno pierwszy i ostatni wiersz \ kolumnę. Trzeba tylko usunąć liczbę dla usuniętego wiersza \, co zabiera czas O(n) lub O(m). to jest krok programowania dynamicznego.

co oznacza złożoność jest O(max(M,N)MN)

Answer 4

stworzyłem małą aplikację, która wykazuje optymalizacji algorytmu wyszukiwania. Daj mi znać, jeśli tego właśnie szukasz.

Uwagi:

1. Program tworzy kwadratową macierz
2. Dla łatwości czytania, używam kolekcji do pracy z danymi. Uważam, że w przetwarzaniu jest przeciążenie, ale staram się tylko podkreślić zasadę.

Oto ona:

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 
     ****************************************************************************************/ 

    } 
}