1. 概要

このチュートリアルでは、ax行列で極小値を見つける問題について説明します。

まず、問題を定義し、それを説明する例を示します。

次に、素朴なアプローチを提示し、それを改善してより良いソリューションを取得します。

2. 問題の定義

x個の異なる整数で構成されるサイズxの行列があるとします。 私たちのタスクは、与えられた行列で極小値を見つけることです。

行列の極小値は、隣接するすべての隣接セルよりも小さい値を持つセルであることを思い出してください。

セルがマトリックス内にある場合、セルには4つの隣接するセルがあります。 さらに、マトリックスの境界上にある場合は、隣接する3つのセルがあります。 最後に、マトリックスのいずれかのコーナーに配置されている場合、隣接するセルは2つだけです。

理解を深めるために例を確認してみましょう。 サイズxの次の行列があるとします。

ご覧のとおり、この例には3つの極小セルがあります。

  1. 、隣接する2つのセルすべての値が。より大きいためです。
  2. 、隣接する4つの隣接セルすべての値が。より大きいためです。
  3. 、隣接する3つの隣接セルすべての値が。より大きいためです。

したがって、この例の答えは、これら3つの極小セルの任意のセルである可能性があります。

3. 素朴なアプローチ

3.1. 本旨

ここでの主なアイデアは、ローカルの最小値に達するまで、現在のセル値よりも小さい値を持つ最小の隣接セルに常に移動することです。

マトリックスを反復処理するには、 DFS （深さ優先探索）を使用します。 セルに到達するたびに、それが極小値であるかどうかを確認します。これは、指定された行列で極小値が見つかったため、完了したことを意味します。 それ以外の場合は、現在のセル値よりも小さい値を持つすべての隣接セルの中で最小値のセルに移動します。

現在のセル値よりも小さい値のセルに移動することは永遠に続くことができないため、最終的にはこれを終了する必要があります。

3.2. 実装

実装を見てみましょう：

最初に、現在のセル値よりも小さい値を持つ最小の隣接セルを返す関数を宣言します。 セルごとに、チェックする必要のある隣接セルが4つあります。

まず、現在の行（）と現在の列（）をそれぞれ表す値を宣言します。 次に、隣接する最小のセルの値を表すを宣言します。 最初に、現在のセルの値をそれに割り当てます。 最後に、隣接する最小のセルを表すを宣言します。 まず、セルと同じになります。

次に、現在の行インデックスが、より上のセルを意味するよりも大きいかどうかを確認します。 次に、そのセルの値がこれまでに取得した最小値よりも小さいかどうかを確認します。 その場合、セルの上にあるセルと等しくなるようにを更新します。 左、右、下の隣接するセルに対して同じプロセスを実行します。

最後に、次のDFSトラバーサルで移動するを返します。

次に、指定された行列の極小値を返す関数を宣言します。 まず、次のDFS呼び出しで移動するを取得します。 次に、セルと等しいかどうかを確認します。これは、セルの値よりも小さい値を持つ隣接セルがないため、セルが極小であることを意味します。 それ以外の場合は、DFSトラバーサルのに移動します。

3.3. 複雑

このアプローチの複雑さは、DFSの複雑さと同じです。です。ここで、はセルの数、は遷移の数です。 したがって、これはセルの数がであるのに対し、遷移の数は。より少し少ないためです。 この複雑さの背後にある理由は、最悪のシナリオで各セルを1回繰り返すためです。 したがって、隣接するネイバーを繰り返し処理します。 合計で、各遷移も1回繰り返します。

4. 分割統治アプローチ

4.1. 本旨

与えられた行列を4つの象限の部分行列に分割します。 極小値がこれら4つのサブ行列の1つに含まれることを保証できます。 極小値が存在する部分行列を見つけるために、とを繰り返して、とのすべての値の中で最小の値を持つセルを取得します。

最小値のセルを取得した後、その（最小の隣接セル）を取得します。 これで、を含むサブ行列にも極小値が含まれます。 これは、極小値が別の部分行列にある場合、またはを交差させる必要があることを意味し、すべてのおよびセルの中で最小の値を持つセルを選択したため、それは不可能であるためです。

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

すべてのセルとセルの中で最小の値を持つを取ります。 次に、それを取得します。 したがって、極小値がサブ行列内にあることを保証できます。 したがって、サブマトリックスの問題を解決し、同じプロセスを繰り返します。

4.2. 実装

実装を見てみましょう：

最初に、指定された行列を取り、その中の極小セルを返す関数を宣言します。

次に、とのインデックスを宣言します。 その後、とを宣言します。これは、とにあるすべてのセルの中で最小の値を持つセルを表します。 そのために、特定の行または列の最小値をそれぞれ返す関数と関数を使用します。

前のアプローチで行ったように、ローカル最小値がどのサブマトリックスにあるかを知るためにを取得します。

次に、がに等しいかどうかを確認します。 この場合、それは極小値であることを意味するので、それを返し、この時点でアルゴリズムを終了します。

ただし、がよりも小さい場合は、極小値が左上または右上のいずれかの部分行列にあることを意味します。 したがって、が未満であるかどうかを確認する必要があります。つまり、左上の部分行列に極小値があるかどうかを確認する必要があります。 それ以外の場合は、右上のサブマトリックスになります。

最後に、が、以上であるかどうかを確認します。これは、極小値が左下または右下のいずれかの部分行列にあることを意味します。 前の条件と同じ方法でチェックします。

4.3. 複雑

ここでの複雑さは。この複雑さの背後にある理由を調べてみましょう。

最初の呼び出しでは、セルを反復処理して。を取得します。 ただし、2番目の呼び出しでは、セルを反復処理します。 その後、セルを繰り返し処理します。

したがって、反復の総数は、に等しくなります。これは、複雑さが。であることを意味します。

5. 結論

この記事では、行列で極小値を見つける問題を紹介しました。 一般的な考え方を説明し、2つのアプローチについて説明しました。

まず、ナイーブなものについて説明しました。 次に、最初のアプローチよりもはるかに高速なアプローチを得るために、それを改善しました。