「アルゴリズムとデータ構造」では、分割統治アルゴリズムの美しさを紹介します。

[[347259]]

序文
この共有の内容は、古典的なアルゴリズムのアイデアである分割統治です。これはアイデアとも、分割統治アルゴリズムとも呼ばれます。より明確に区別するために、以下では「分割統治法」と呼びます。

分割統治法が何であるか分からない場合、または少しは知っているがバックトラッキングをどのように実装すればよいか分からない場合は、この記事を読むとよいでしょう。

分割統治アルゴリズムについての私の理解:

その基本的な考え方は、サイズ N の問題を、互いに独立しており、元の問題と同じ特性を持つ K 個の小さなサブ問題に分解することです。
サブ問題の解決策を見つけることで、元の問題の解決策を得ることができます。これは、異なる目標を持つプログラムを完了するためのアルゴリズムとして理解できます。
二分法は、多くの場合、分割統治の考え方です。

それでは、以下の点を中心に分割統治アルゴリズムを紹介します👇

基本的な考え方
適用可能な状況と解決される古典的な問題
典型的な例

分割統治の基本的な考え方
分割統治法を一言でまとめると👇

元の問題を、規模は小さいが構造は元の問題に似ている n 個のサブ問題に分割し、これらのサブ問題を再帰的に解決し、その結果を順番にマージして、最終的に元の問題の解決策を得ます。

具体的には、3つのステップに分けられるようです👇

分解: 解決する問題をいくつかの小さな類似した問題に分割します。
解決策: サブ問題が十分に小さな部分に分割されている場合は、より簡単な方法を使用して解決します。
マージ: 元の問題の要件に従って、サブ問題のソリューションがレイヤーごとにマージされ、元の問題のソリューションが形成されます。

実際、その考え方は同じで、直接解決するのが難しい大きな問題を、いくつかの小規模な類似の問題に分割し、それらを一つずつ解決して分割統治によって征服するというものです。

分割統治アプリケーション
分割統治法を使用して問題を解決するかどうかは、分割統治法のいくつかの特性を理解できるかどうかによって決まります。

問題をある程度まで縮小し、解決すべきより小さな問題に変えることができます。
いくつかの小さな問題に分解した後、規模は小さくなり、それらは同じ種類になります。この場合、問題は最適なサブ構造になるはずです。
この問題から分解されたサブ問題の解決策を使用して、それらをこの問題の解決策に統合します。
分解されたサブ問題は互いに独立しており、つまり、サブ問題間に共通のサブ問題は存在しません。

これらの機能について説明しましょう。

最初の特性:問題の計算の複雑さは一般に問題のサイズに応じて増加するため、ほとんどの問題はこの要件を満たしています。

2つ目の特徴は、分割統治法を適用する前提がこれを満たすことです。これは、ある程度、再帰的思考の適用を反映していると理解できます。

3 番目の特性: これは分割統治法の鍵となるはずです。分割統治法を使用できるかどうかは、問題が 3 番目の特性を持っているかどうかに完全に依存します。問題が 1 番目と 2 番目の特性を持っているが 3 番目の特性を持っていない場合は、貪欲法または動的計画法の使用を検討できます。

4 番目の特徴: 分割統治法の効率性に関係します。サブ問題が独立していない場合、分割統治法では多くの不必要な作業を実行し、共通のサブ問題を繰り返し解決する必要があります。この時点で分割統治法を使用することもできますが、一般的には動的計画法を使用する方がよいでしょう。

分割統治法の特徴を理解した上で、この考え方を使って問題を解決する古典的な問題をいくつか見てみましょう👇

古典的な問題を解決する分割統治法
このアイデアはどのような状況で問題を解決するために使用できますか？以下はインターネットから収集したものです👇

（１）二分探索

（２）大きな整数の乗算

（３）シュトラッセン行列の乗算

（４）チェス盤カバー

（５）マージソート

（6）クイックソート

（７）線形時間選択

（８）最近点ペア問題

（9）ラウンドロビンスケジュール

（10）ハノイの塔

私が言及したいのは、分割統治の考え方を完成させ、大きな問題を分解し、さまざまな規模の小さな問題を解決し、最後にそれらをマージするマージソートです。マージソートのコードを見てみましょう👇

マージソート

マージソートの考え方については、どのように実装されているのでしょうか。分割統治の考え方が採用されていることは、ソートに関する前の章で説明しました。どのように実装されているかはおわかりでしょう。ここでは詳しく説明しません。

2 例
次に、3つの質問を例に、分割統治の考え方を使って問題を解決する方法を見ていきます👇

最大部分列合計 ⭐

リンク: 最大部分列合計

整数配列 nums が与えられた場合、最大の合計を持つ連続したサブ配列 (サブ配列には少なくとも 1 つの要素が含まれます) を見つけ、その最大の合計を返します。

例：

入力: [-2,1,-3,4,-1,2,1,-5,4] 出力: 6

説明: 連続するサブ配列 [4,-1,2,1] の合計が最大で、6 になります。

高度な：

O(n) の複雑度を持つソリューションを実装した場合は、より洗練された分割統治ソリューションを使用してみてください。

出典: LeetCode リンク: https://leetcode-cn.com/problems/maximum-subarray 著作権は LeetCode Network に帰属します。商用目的での複製については、正式な許可を得るためにお問い合わせください。非商用目的での複製については、出典を明記してください。

まず、この問題をO(n)の計算量で解けるかどうかを見てみましょう。実際、よく考えてみると、単純な

さらに、私たちは分割統治法を使ってこの問題を解決しようとしています。配列の最大部分列合計の場合、答えへの寄与は次のケースのみになります 👇

左側に表示されます
右側に表示されます
真ん中に現れて真ん中を通り抜けます。

では、これを再帰的に処理できるでしょうか。左側と右側に現れる答えを 1 つの状況として扱い、再帰的に処理することができます。もちろん、再帰の終了は明らかです。再帰配列の長さが 1 になったら、再帰を終了する必要があります。

答えが真ん中に出てくる場合は計算で答えが導き出せるので、しっかり考えましょう。次は書き方を見てみましょう👇

分割統治連続最大和

もちろん、この問題は動的プログラミングの考え方で解決した方が理解しやすいです👇

//dp[i]はnums[i]で終わるnums内の最大部分列の合計を表します

連続和の動的計画法

コードはこちらをクリック☑️

2D 行列の検索 II ⭐⭐

リンク: 2D マトリックスの検索 II

mxn 行列 matrix 内のターゲット値 target を検索するための効率的なアルゴリズムを記述します。このマトリックスには次のプロパティがあります。

各行の要素は左から右へ昇順で並べられます。各列の要素は上から下へ昇順で並べられます。例：

既存のマトリックスマトリックスは次のとおりです。

[ [1、4、7、11、15]、[2、5、8、12、19]、[3、6、9、16、22]、[10、13、14、17、24]、[18、21、23、26、30] ]

target = 5 の場合、true を返します。

target = 20 の場合、false を返します。

出典: LeetCode リンク: https://leetcode-cn.com/problems/search-a-2d-matrix-ii 著作権は LeetCode Network に帰属します。商用目的での複製については、正式な許可を得るためにお問い合わせください。非商用目的での複製については、出典を明記してください。

この問題のタイトルは非常に明確です👉 行列の各行は左から右に昇順になっており、各列も上から下に昇順になっています。行列内の数字を見つけます。

もちろん、私たちにはシンプルなアイデアがあります👇