1. 概要

このチュートリアルでは、分割統治法と動的計画法という2つの非常に一般的なアルゴリズムパラダイムについて説明します。

基本的な考え方から始めて、各パラダイムの例を示します。 最後に、それらの主な違いを示します。

2. 分割統治法

「分割統治」という表現は、政治社会学でよく知られており、もともとはローマの統治者によって「分割統治法」として使用されていました。 これは、パワーと難易度に影響を与えるために、要素をサブ要素に分割することに焦点を当てた戦略です。

このアイデアに触発されて、研究者は分割統治アプローチを設計しました。 分割統治アルゴリズムの最初のフェーズは、主要な問題を分割または分割することです。最初のフェーズの主なアイデアは、特定の問題をより小さなインスタンスまたはサブ問題に分割することです。  分割が不可能になる段階に達するまで、各サブ問題をさらに小さなサブ問題に分割します。

分割統治アルゴリズムの第2フェーズは、第1フェーズで生成されたサブ問題を解決することです。この段階では、多くのサブ問題を再帰的に解決します。 ただし、分割フェーズ後に独自に解決済みとしてマークされるため、サブ問題を解決する必要がない場合もあります。

分割統治アルゴリズムの最終段階は、サブ問題の解決策をマージすることです。元の問題の解決策が得られる段階に達するまで、サブ問題の解決策は再帰的にマージされます。 ：

分割統治アルゴリズムは、ソリューションの時間計算量を大幅に削減するのに役立ちます。

3. 分割統治アルゴリズムの例

二分探索アルゴリズム、並べ替えアルゴリズムなど、分割統治パラダイムにはいくつかのアプリケーションがあります。

ここでは、分割統治アルゴリズムが実際にどのように機能するかを説明するために、二分探索アルゴリズムを紹介します。 数値の入力配列が与えられた場合、入力配列にが存在するかどうかを確認する必要があります。 アルゴリズムは、入力配列で数値が見つかった場合はTRUEを返し、それ以外の場合はFALSEを返します。 さらに、この例では、入力配列がソートされていると想定しています。

分割統治パラダイムに従って、入力配列を2つのサブ配列に分割します。 さらに、さらに分割できないインスタンスに到達するまで、サブ配列をより小さなインスタンスに分割し続けます。 この例では、要素は入力配列に存在します。 したがって、アルゴリズムは出力としてTRUEを返します。

重要な部分は、入力配列全体にアクセスする必要がないことです。 元の問題の解決策を見つけるために、入力配列の一部のみにアクセスします。 時間計算量をに減らします。

4. 動的計画法アプローチ

動的計画法は一般的なアルゴリズムのパラダイムであり、漸化式を使用して解を見つけます。  問題をより小さなサブ問題に分解するため、分割統治戦略に似ています。

主な違いは、動的計画法では、サブ問題が相互に依存していることです。したがって、サブ問題の結果を保存し、類似または重複するサブ問題の将来の参照で使用します。実行時間を短縮します。

したがって、動的計画法は、主な問題を小さなサブ問題に分割でき、小さなサブ問題が本質的に重複している場合に適しています。具体的には、動的計画法は、分割統治法。

現在のサブ問題の解を計算する前に、以前の解を調べます。 以前に計算されたサブ問題のいずれかが現在のものと類似している場合、そのサブ問題の結果を使用します。 最後に、サブ問題の解決策をマージして、元の問題の解決策に到達します。

5. 動的計画法アルゴリズムの例

このセクションでは、フィボナッチ数の問題を取り上げ、動的計画法を使用して問題を解決する方法について説明します。フィボナッチ関数は数学的に次のように表すことができます。

   

   

ここに、ユーザー入力があります。 動的計画法のアプローチを使用してフィボナッチ関数を解く方法を説明するために、入力値を取得します。 最初のフェーズでは、元の問題をサブ問題に分割します。 分割統治とは異なり、サブ問題を繰り返し計算し、将来の使用に備えてソリューションを保存します。

最後に、サブ問題の解決策を組み合わせて、メイン問題の解決策を実現します。

6. 分割統治法と動的計画法

これで、両方のアルゴリズムのパラダイムの背後にある理論的な考え方がわかりました。 いくつかの点でそれらは似ていますが、アプローチにも違いがあります。 このセクションでは、これまでのすべての説明を要約し、主な違いを表に列挙します。

7. 結論

これらの2つの戦略は類似していますが、特定の用途では異なります。

どちらのアプローチもソリューションの複雑さを軽減するのに役立ちますが、逆の場合もあります。 したがって、問題を解決するために適用する適切な戦略を賢明に選択することは、研究者の使命であり続けます。

このチュートリアルでは、分割統治法と動的計画法のパラダイムの基本的な考え方について説明しました。 最後に、各アプローチの例を示し、主な違いを表に列挙しました。