1. 概要

このチュートリアルでは、0と1のみを含む行列で1で満たされた最大の正方形のサイズを見つける方法について説明します。

まず、問題を定義します。 次に、それを説明するための例を示します。

その後、この問題を解決するための4つの異なるアプローチを紹介します。

2. 問題の定義

サイズのバイナリ行列（行と列を含む）が与えられます。 行列の各セルには、0または1のいずれかに等しい値があります。 サブマトリックスでいっぱいのサブマトリックスの最大辺の長さを見つけるように求められます。

理解を深めるために、次の例を見てみましょう。

サブマトリックスを2つのタプルとで表します。これらはそれぞれ左上隅と右下隅の位置を表します。

ご覧のとおり、サブマトリックスは、1つでいっぱいの最大の正方形のサブマトリックスです。 サイズはに等しいので、与えられた例の答えは、正方形の辺の長さを表すです。

3. ブルートフォースアプローチ

3.1. 本旨

このアプローチの考え方は、指定されたマトリックスのすべてのセルをループすることです。 セルごとに、左上隅として固定し、可能なすべての正方形の長さを確認します。

それぞれの長さについて、現在の固定セルを表す左上隅の座標にを追加することにより、右下隅を取得します。 現在の正方形が1でいっぱいかどうかを確認するために、このサブマトリックスのすべてのセルを反復処理して、それらが1に等しいかどうかを確認します。

最後に、現在の正方形が有効である場合、現在の長さで答えを最大化して、最大の正方形の長さを1でいっぱいにします。

3.2. フルスクエアをチェックする

まず、与えられた正方行列が正方行列で満たされているかどうかをチェックする関数を実装しましょう。

サブマトリックス内の各セルを反復処理します。 現在のセルの値がゼロに等しい場合、を返します。

それ以外の場合、最後に到達してゼロが見つからない場合は、サブマトリックスが1でいっぱいであることを意味します。 その結果、を返します。

3.3. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、を宣言します。これにより、問題の回答が保存されます。 次に、指定された行列の各セルを反復処理し、正方形の部分行列の左上隅として固定します。

次に、可能なすべての長さをチェックしようとします。 現在の長さが行列に収まらない正方形を生成する場合、ループから抜け出します。

それ以外の場合は、左上隅と右下隅がある正方形の部分行列がいっぱいであるかどうかを確認します。 もしそうなら、それは一辺の長さがに等しい正方形があることを意味します。 したがって、前の回答と現在の長さの間の最大値に等しくなるように回答を最大化します。

最後に、は最大の正方形の長さでいっぱいになります。

3.4. 複雑さ

このアルゴリズムの複雑さはです。ここで、は行数、は列数、は正方形の辺の可能な最大長であり、最悪の場合はに等しくなります。

この複雑さの背後にある理由は、に等しい複雑さで各セルを1回繰り返すためです。 一方、セルごとに、に等しい複雑さで可能なすべての長さを試します。

さらに、すべての長さについて、正方形が1でいっぱいであるかどうかを確認します。これは、に等しい複雑さを持っています。

これにより、合計の複雑さはに等しくなります。

4. 動的計画法の最適化

4.1. 本旨

このアプローチでは、前のアプローチと同じアイデアを使用します。 ただし、関数を最適化し、の代わりに複雑に実行するようにします。

動的計画法の最適化である2Dプレフィックス合計手法を使用して、一定の時間計算量で部分行列の合計を取得します。 この手法の主なアイデアは、サブ行列（1、1）、（i、j）内のすべての要素の合計を内部に格納する行列を作成することです。

このマトリックスを作成する式は次のとおりです。

   

部分行列（1、1）、（i、j）の合計は、部分行列（1、1）、（i、j – 1）と（1、1）、（ i – 1、j）。 ただし、この場合、（1、1）、（i – 1、j – 1）の合計を2回加算しました。 したがって、回答から削除します。 また、現在のセル（i、j）を含めなかったため、プレフィックス値に追加します。

特定の部分行列の合計を取得する場合は、右下隅の合計を取得します。

次に、サブ行列の合計に対応する減算を行います。 また、サブ行列の合計を表す減算を行います。

最後に、前の2つのサブマトリックスを削除したときに、このサブマトリックスを2回削除したため、サブマトリックスの合計であるを追加します。

次の例を見てみましょう。

サブマトリックス（2、2）、（4、4）の合計は、次の2Dプレフィックス値を使用して計算できます。

   

4.2. アルゴリズム

関数の拡張された実装を見てみましょう。

この関数は、左上隅と右下隅をパラメーターとして受け取ります。 次に、サブマトリックスのセル数を表すサブマトリックスの面積を計算します。

その後、2Dプレフィックス合計手法を使用して、サブマトリックス内の要素の合計を取得します。これは、サブマトリックス内の要素の数を表します。

最後に、の値がの値（1の数がセルの数に等しい）に等しい場合、それは指定されたサブマトリックスが1でいっぱいであることを意味します。 そうでなければ、そうではありません。

4.3. 複雑さ

このアルゴリズムの複雑さはです。ここで、は行数、は列数、は正方形の辺の可能な最大長であり、最悪の場合はに等しくなります。

この複雑さの背後にある理由は前のアプローチと同じですが、サブマトリックスが複雑さの1つでいっぱいであるかどうかをチェックする代わりに、一定時間でそれを行いました。

さらに、アルゴリズムを開始する前に、配列の値を計算しますが、これはに等しい複雑さであり、アルゴリズム自体の複雑さよりも小さくなります。

5. 二分探索アプローチ

5.1. 本旨

このアプローチでは、バイナリ検索アルゴリズムを使用して、。で有効な最大長を見つけます。

ここで二分探索が機能する理由は、左上隅を反復処理しているときに、サイズが1でいっぱいの正方形がある場合、サイズのすべての正方形も1で埋められることを意味します。 その理由は、サイズの2乗がサイズの2乗の部分行列であるためです。

一方、サイズの正方形で埋められていない正方形がある場合、それはサイズのすべての正方形も1で埋められていないことを意味します。

5.2. アルゴリズム

実装を見てみましょう：

最初に、を宣言します。これにより、問題の回答が保存されます。 次に、指定された行列の各セルを反復処理し、正方形の部分行列の左上隅として固定します。

次に、二分探索を使用して最大有効長を見つけます。 二分探索アルゴリズム中に、現在の長さが有効である場合（1でいっぱいの正方形が得られる場合）、を最大化して、より長い長さを探します。 それ以外の場合、現在の長さは無効であり、正方形でいっぱいになるより短い長さを見つけようとします。

最後に、は最大の正方形の長さでいっぱいになります。

5.3. 複雑さ

このアルゴリズムの複雑さはです。ここで、は行数、は列数、は正方形の辺の可能な最大長であり、最悪の場合はに等しくなります。

この複雑さの背後にある理由は、機能を強化した以前のアプローチと同じです。 それでも、可能なすべての長さをループする代わりに、の代わりに複雑さのある二分探索手法を使用して完全な長さを見つけました。

6. 2つのポインターアプローチ

6.1. 本旨

ここでの主な考え方は、セルごとに完全な長さの検索を何度も繰り返す必要がないということです。

代わりに、有効な長さが見つかった場合、長さでいっぱいの正方形がすでにあるため、長さを再度確認する必要はありません。 今、私たちはただものでいっぱいのより大きな正方形を探しています。

6.2. アルゴリズム

実装を見てみましょう：

最初に、を宣言します。これは、現時点での最大長を表します。 また、それは私たちの問題への答えになります。

次に、指定された行列の各セルを反復処理し、正方形の部分行列の左上隅として固定します。 次に、現在の長さの正方形でいっぱいの正方形があり、マトリックスの境界を超えていない限り、を増やしてより大きな正方形を見つけます。

最後に、値は1でいっぱいの最大の正方形の長さになります。

6.3. 複雑さ

このアルゴリズムの複雑さはです。ここで、は行数、は列数、は正方形の辺の可能な最大長であり、最悪の場合はに等しくなります。

この複雑さの背後にある理由は、の複雑さで各セルを1回繰り返すためです。

さらに、の値を減らすことはありません。 代わりに、完全な長さを見つけるために、有効な長さを見つけたときに以前のすべての長さを再チェックしないため、各長さを最大で1回繰り返します。

7. 結論

この記事では、1でいっぱいの最大の正方形を見つける問題を紹介しました。

まず、問題を説明する例を示しました。 次に、それを解決するための4つの異なるアプローチを示しました。

最後に、それぞれのアプローチの時間計算量が前のアプローチよりも優れている状態で、それらの実装について説明しました。