分割統治法と動的計画法の違いは何ですか

分割統治法と動的計画法は、問題を解決するための2つのアルゴリズムまたはアプローチです。分割統治アルゴリズムは、問題をサブ問題に分割し、それらの解決策を組み合わせて、元の問題の解決策を見つけます。ただし、動的計画法では、サブ問題を個別に解決することはできません。サブ問題の回答を保存して、同様の問題に使用します。

分割統治法、動的計画法

分割統治とは

分割統治法は、主要な問題を小さなサブ問題に分割します。サブ問題は何度も何度も分割されます。ある時点で、サブ問題をさらに分割できない段階があります。次に、各サブ問題を個別に解決できます。最後に、すべてのサブ問題の解決策を組み合わせて、主要な問題の解決策を得ることができます。

分割統治には3つの主要なステップがあります。以下のとおりです。

分割（ブレーク） –主な問題をサブ問題のコレクションに分割することを含みます

征服（解決） –各サブ問題を個別に解決する必要があります

結合（マージ） –サブ問題の解決策を結合して、メイン問題の解決策を取得します

動的計画法とは

動的計画法は、主要な問題をより小さなサブ問題に分割しますが、サブ問題を独立して解決するわけではありません。同様のサブ問題を解決するときに使用するサブ問題の結果を格納します。サブ問題の結果を保存することを暗記と呼びます。現在のサブ問題を解決する前に、前のサブ問題の結果をチェックします。最後に、すべてのサブ問題の結果をチェックして、最適なソリューションまたは最適なソリューションを見つけます。この方法は、答えを何度も計算しないので効果的です。通常、動的計画法が最適化に使用されます。

動的計画法の要素は次のとおりです。

単純なサブ問題 –元の問題を同様の構造を持つ小さなサブ問題に分割します

問題の最適な下部構造 –主な問題の最適解は、その副問題の最適解の範囲内にあります

重複するサブ問題 –同じサブ問題を何度も解決する状況

分割統治法と動的計画法の違い

意味

分割統治法は、問題を直接解決できるほど単純になるまで、同じタイプまたは関連するタイプの2つ以上のサブ問題に再帰的に分解するアルゴリズムです。ただし、動的計画法は、重複するサブ問題と最適な部分構造特性を持つ問題のクラスを効率的に解決するのに役立つアルゴリズムです。

タイプ

分割統治法と動的計画法の主な違いは、分割統治法は再帰的であるのに対し、動的計画法は非再帰的であるということです。

サブ問題

分割統治では、サブ問題は互いに独立しています。ただし、動的計画法では、サブ問題は相互に依存しています。したがって、これは分割統治法と動的計画法のもう1つの大きな違いです。

時間の消費

時間の消費は、分割統治法と動的計画法のもう1つの違いです。分割統治法は、各サブ問題を個別に解決します。したがって、より時間がかかります。一方、動的計画法は、前のサブ問題の答えを使用します。したがって、時間はかかりません。

効率

効率はまた、分割統治法と動的計画法の違いを生みます。動的計画法は、分割統治よりも効率的です。

アプリケーション

マージソート、クイックソート、およびバイナリ検索では分割統治法を使用し、行列の連鎖乗積と最適なバイナリ検索ツリーでは動的計画法を使用します。

結論

分割統治法と動的計画法の主な違いは、分割統治法はサブ問題の解を組み合わせて主問題の解を取得するのに対し、動的計画法はサブ問題の結果を使用して主問題の最適解を見つけることです。

リファレンス：

1.「DAA分割統治法の紹介–Javatpoint」。 Www.javatpoint.com、ここから入手可能2。「動的計画法の紹介–Javatpoint」。 Www.javatpoint.com、こちらから入手可能3。動的計画法|設計とアプリケーションの手順|、Education 4u、2018年4月2日、こちらから入手可能4。「動的計画法」、Programiz。 com、ここで入手できます。

画像提供：

1.英語版ウィキペディアのVineetKumarによる「マージソートアルゴリズム図」– Commons Wikimedia2を介してCommonsHelper（パブリックドメイン）を使用して、EricBaumanによってen.wikipediaからCommonsに転送されました。「フィボナッチ動的計画法」en：User：Dcoatzee著、User：Stanneredによる追跡– en：Image：Fibonacci動的計画法.png（パブリックドメイン）コモンズウィキメディア経由