algorithm - 1 と 0 の数が等しい最大の部分行列

Question

mxn0 と 1 のみを含むサイズの行列が与えられます。1 と 0 の数が等しい最大のサブマトリックスを見つける必要があります。ブルート フォース アプローチはO(m^2*n^2)、これよりも優れた方法はありますか?
動的計画法を適用しようとしましたが、最適な部分構造が見つかりませんでした。

この問題の同様の 1 次元バージョンがここで議論されたと
思います。
余分なスペースを使用するO(n)ソリューションがあります。

Answer 1

このアルゴリズムは、行と列が連続していて、高さと幅の積が可能な限り大きい部分行列を検索することを前提としています。

次の前処理から始めます。

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

行の各ペア (i, j) に対して、次の操作を行います。

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

検索アルゴリズムの最適化を示す小さなアプリケーションを作成しました。これがあなたが探しているものかどうか教えてください。

ノート：

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

    }
}

Answer 3

m < n と仮定すると、O(M * M * N) アルゴリズムを使用できます。そして、すべての 0 を -1 で置き換えると、合計が 0 である最大のサブマトリックスを見つけるだけです。

1. 各行のセグメント (i, j) の合計を取得します。それらを c1、c2、c3....、cn と定義します。参照したアルゴリズムによって O(n) アルゴリズムを実行できます。
2. ステップ 1 を M * M 回実行して、合計が 0 になる最大のサブマトリックスを取得する必要があるため、複雑さは O(M * M * N) になります。

Answer 4

サブマトリックスは、元のマトリックスの連続する行\列のみを使用して形成されると仮定します（つまり、最初の\最後の行または列を削除することにより）。

このように、行列は次のように表すことができます。

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

元の行列の次元が M x N の場合、

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

変数rowとcolはそれぞれMとN可能な値を持ちます。これはO(MxN)、そのような行列が存在することを意味します。

アルゴリズムの考え方

1. 行列(m, n)をキューから取り出す
2. テスト 。成功した場合、出力行列
3. (m, n-1)すべての行列を構築し(m-1, n)、キューに入れる
4. 1に戻ります。

今、2 つのポイントがあります。

• 次元を減らすと、可能な行列は 4 つだけになります (行を削除して 2 つ、列を削除して 2 つ)
• 最初と最後の行\列のいずれかを削除して、サブ マトリックスを作成します。削除した行\列のカウントを削除するだけで済みますが、これには時間がかかりO(n)ますO(m)。これが動的計画法のステップです。

つまり、複雑さはO(max(M,N)MN)