データ構造-分割統治

分割統治法では、手元の問題をより小さなサブ問題に分割し、各問題を個別に解決します。サブ問題をさらに小さなサブ問題に分割し続けると、最終的にはそれ以上分割できない段階に達する可能性があります。それらの「原子的」で可能な最小のサブ問題(分数)が解決されます。元の問題の解決策を得るために、すべてのサブ問題の解決策が最終的にマージされます。

大まかに理解できます divide-and-conquer 3段階のプロセスでアプローチします。

分割/分割

このステップでは、問題をより小さなサブ問題に分割します。サブ問題は、元の問題の一部を表す必要があります。このステップでは、通常、再帰的なアプローチを使用して、サブ問題がさらに分割できなくなるまで問題を分割します。この段階で、サブ問題は本質的にアトミックになりますが、それでも実際の問題の一部を表しています。

征服/解決

このステップには、解決すべき小さなサブ問題がたくさんあります。一般に、このレベルでは、問題はそれ自体で「解決済み」と見なされます。

マージ/結合

小さなサブ問題が解決されると、この段階では、元の問題の解決策が定式化されるまで、それらを再帰的に結合します。このアルゴリズム的アプローチは再帰的に機能し、征服とマージのステップは非常に近く機能するため、1つに見えます。

次のコンピュータアルゴリズムはに基づいています divide-and-conquer プログラミングアプローチ-

  • マージソート
  • クイックソート
  • 二分探索
  • Strassenの行列乗算
  • 最も近いペア(ポイント)

コンピュータの問題を解決するために利用できるさまざまな方法がありますが、上記は分割統治法の良い例です。