1. 概要

分割統治戦略では、再帰の各レベルで3つのステップ（分割統治、征服、結合）を適用することにより、問題を再帰的に解決します。

このチュートリアルでは、それらについて詳しく説明します。

2. 分割統治アルゴリズムの手順

2.1. 分ける

「分割」は、分割統治戦略の最初のステップです。 名前からわかるように、このステップでは、問題が解決できるほど小さくなるまで、問題を小さなサブ問題に分割します。 このステップでは、サブ問題は小さくなりますが、それでも実際の問題の一部を表します。

上記のように、分割統治アルゴリズムを実装するために再帰を使用します。 再帰的アルゴリズムは、より小さなまたはより単純な入力値でそれ自体を呼び出します。 これを再帰的な場合と呼びます。 したがって、分割ステップを実装するときに、問題をより小さなサブ問題に分割する再帰的なケースを決定します。

2.2. 征服する

次に、サブ問題を直接解決する「征服」ステップがあります。 これまでに、入力を可能な限り最小の部分に分割しました。次に、基本的な操作を実行してそれらを解決します。

再帰的なベースケースを指定することにより、再帰を伴う征服ステップを実装します。 サブ問題が十分に小さくなり、再帰しなくなると、再帰は「ボトムアウト」し、ベースケースに到達したと言います。 基本ケースに到達したら、サブ問題を解決します。

2.3. 混ぜる

最後に、分割統治戦略の最後のステップである「結合」に到達します。

このステップでは、サブ問題の解決策を組み合わせて、問題全体を解決します。 基本ケースの解決から返される出力は、より大きなサブ問題の入力になります。

したがって、基本ケースに到達した後、小さなサブ問題から返された入力を使用して、大きなサブ問題を解決するために作業を開始します。 このステップでは、征服ステップからの出力をマージして、より大きなサブ問題を解決します。  元の問題全体を解決するまで、下から上に伝播します。

2.4. フロー全体

分割統治の戦略を視覚化するために、手順全体のフローチャートを見てみましょう。

ご覧のとおり、最初に問題を分割し、次にそれを克服して完全なソリューションに結合します。

3. 分割統治アルゴリズムの複雑さ

アルゴリズムにそれ自体への再帰呼び出しが含まれている場合、その実行時間を次のように表すことができます。 漸化式 また 再発、サイズの問題に関する全体的な実行時間を記述します n 小さい入力での実行時間の観点から。

分割統治アルゴリズムの実行時間の再発は、基本的なパラダイムの3つのステップから外れます。

いつものように、 サイズの問題の実行時間になる 。 問題のサイズが十分に小さい場合は、 一定の 、簡単な解決策には一定の時間がかかります。 .

問題を分割すると、次のようになります。 サブ問題、それぞれが オリジナルのサイズ。 時間がかかる   サイズの1つのサブ問題を解決する 、だから時間がかかる 解決する そのうちの。

取ったら 問題をサブ問題に分割する時間と サブ問題の解決策を元の問題の解決策に組み合わせるとき、再発が発生します。

4. 分割統治アルゴリズムの利点

分割統治パラダイムの最初の、そしておそらく最も認識できる利点は、困難な、時にはNPの問題さえも解決できるという事実です。

難しい問題を与えられることは、それを解決する方法がわからない場合、しばしば落胆する可能性があります。 ただし、分割統治法を使用すると、問題を簡単に解決できるサブ問題に分割するため、難易度が低くなります。

このパラダイムのもう1つの利点は、他の効率的なアルゴリズムを見つけるのに役立つことが多いことです。 実際、クイックソートとマージソートのアルゴリズムを見つける上で中心的な役割を果たしました。

また、メモリキャッシュを効果的に使用します。 この理由は、サブ問題が十分に単純になると、低速のメインメモリにアクセスしなくても、キャッシュ内で解決できるため、時間を節約し、アルゴリズムをより効率的にすることができます。

また、場合によっては、反復法よりも丸められた算術を使用した計算で、より正確な結果を生成することもできます。

分割統治戦略では、問題を互いに独立して実行できるサブ問題に分割します。 したがって、この戦略を並列実行に適したものにします。

5. 分割統治アルゴリズムのデメリット

この種のアルゴリズムで最も一般的な問題の1つは、再帰が遅いという事実です。これは、場合によっては、この分割統治プロセスの利点を上回ります。

これに関するもう1つの懸念は、という事実です。特に、nが大きい場合は、基本的な反復アプローチよりも複雑になることがあります。

言い換えれば、誰かが大きな数を足し合わせたい場合、それらを足し合わせるための単純なループを作成するだけであれば、数を2つのグループに分割して、これらを足し合わせるよりもはるかに簡単なアプローチであることがわかります。グループを再帰的に作成し、2つのグループの合計を合計します。

6. 実例

6.1. 二分探索アルゴリズム

二分探索は分割統治アルゴリズムです。 すべての分割統治アルゴリズムと同様に、配列を2つの小さなサブ配列に分割します。 次に、サブアレイの1つを破棄し、他のサブアレイで検索を続行します。

検索キーを配列の中央にある要素と比較します。  この比較により、破棄するサブアレイが決定されます。  検索キーの値が配列の中央にある項目よりも小さい場合、間隔は下のサブ配列に狭められます。 それ以外の場合は、上位のサブ配列に絞り込みます。

このアルゴリズムを使用するには、配列をソートする必要があります。

6.2. マージソートアルゴリズム

The マージソート アルゴリズムは分割統治パラダイムに厳密に従います。 マージソートアルゴリズムでは、divide n-の2つのサブシーケンスにソートされる要素シーケンス n = 2 それぞれの要素。 次に、マージソートを使用して、2つのサブシーケンスを再帰的にortします。 最後に、 ソートされた回答を生成するための2つのソートされたサブシーケンス。

7. 結論

この記事では、再帰を使用して分割統治の戦略を検討しました。