分割統治法

分割統治法（ぶんかつとうちほう、Divide and conquer algorithm, D&C）は、そのままでは解決できない問題を小さな問題に分割することで、最終的に問題を解決しようとする考え方。また、その方法やアルゴリズム。

クイックソートやマージソートに代表されるようなソートでよく使われている。また、構造化プログラミングでも、この考え方に基づいている。

分割統治法のアルゴリズム

アルゴリズムとしての分割統治法の実装は、再帰呼び出しを使って実装することができる。以下のような手続きになる。

function hoge(x)
  if hoge(x)の求値が簡単 then
    return 簡単な方法で解いたhoge(x)の値
  else
    x を y1, y2 といった複数個のパラメータに分割。(小さな副問題に分割)
    hoge(y1), hoge(y2) を再帰呼び出し
    return hoge(y1) と hoge(y2) の値から求めた hoge(x) の値

なおここで小さな副問題に分割するときに副問題を解くアルゴリズムは自由に選択できる。そのため分割統治法を使ったアルゴリズムには、他のアルゴリズムを組み込むことも出来る。

分割統治法は、再帰の際に同じ副問題を複数回解いてしまう場合があり、こうした場合にはこれが原因で計算コストが指数的に発散してしまう事があるという問題を抱える。この問題は、すでに解いた副問題をメモリ上に記憶する事で解決できる(動的計画法)。

また上のように再帰呼び出しを使った処理は現在の状態を格納するスタックを内部的に使用しているので、メモリを消費し、実行速度が遅くなる。しかし、一部の特定のパラメータを格納するスタックやキューなどを使って再帰呼び出しを使わないでループなどで実装することも可能である。

分割統治法のアルゴリズム

関連項目