分割統治法と動的計画法

はじめに

アルゴリズムについての学習の中で「分割統治法」と「動的計画法」という言葉が出てきたが、これらの違いをすぐに忘れてしまうため自分用のメモとして記事に残す。

分割統治法とは

問題をより小さな部分問題に分割し、それらを個別に解くことで元の問題を解決するというアプローチ。

分割統治法の特徴

• 一般的に再帰的に実装される
• 問題の解決は、下記3ステップで行われる
  1. 問題の分割
  2. それぞれの問題の解決
  3. 結果の結合
• 代表例は、クイックソート、マージソート、高速フーリエ変換（FFT）など

動的計画法とは

問題をより小さな部分問題に分解し、それぞれを一度だけ解くアプローチ。

動的計画法の特徴

• 部分問題の解を記憶し、それを必要とする他の部分問題で再利用する
  ⇨同じ部分問題を何度も解くのを避け、計算効率を大幅に改善

• 下記の場合に特に有効

  • 問題が最適部分構造を持つ
    （大きな問題の解が部分問題の解から構築できる特性）
  • 問題が重複する部分問題を持つ
    （同じ部分問題が何度も出現する特性）

• 代表例は、フィボナッチ数列、ナップサック問題、最長共通部分列（LCS）など

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

部分問題の扱い方

分割統治法 部分問題は独立しており、それぞれが個別に解かれる
動的計画法 同じ部分問題が何度も出現することを前提とし、それらを再利用することで計算効率を改善する

アプローチ方法

分割統治法 再帰的なアプローチを取り、大きな問題を小さな部分問題に分割して解決
動的計画法 問題のサイズを徐々に増やしながら問題を解決する、ボトムアップのアプローチを取る

参考