分割統治法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

分割統治法(ぶんかつとうちほう、Divide-and-Conquer method)は、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。

擬似コード[編集]

分割統治法を擬似コードによって表現すると、以下のような再帰呼出しを使ったものとなる。また、分割統治法になっている何らかのアルゴリズムを実装すると、その基本的な骨組みがこのようになる。

function conquer(x)
  if xは簡単にconquerできる then
    return conquerの結果
  else
    (x1, x2, ...) := divide(x)     // 複数の小さな副問題に分割
    (y1, y2, ...) := (conquer(x1), conquer(x2), ...)  // 再帰
    return synthesize(y1, y2, ...)  // 各副問題の解を合成(最大値を選ぶ、等)

具体的なアルゴリズムのサンプルとしては、マージソートの記事などを参照。

その他[編集]

分割統治法は、再帰の際に同じ副問題を複数回解いてしまう場合があり、そうした場合にはそれが原因で計算コストが、計算を終えるのが非現実的になるほどに増加(例えば指数的に発散英語版して)しまう事がある。この問題はメモ化で解決できることがある。最初からメモ化を組込んだ手法の例に、動的計画法がある。

(以下はこの手法に限らず一般的な話であるが)再帰呼出しを使ったプログラムでは、再帰が深くなるとスタックが大きく成長し、メモリが足りなくなったり最悪の場合はスラッシングを起こす。再帰をループに書換える手法もあるが、直接の末尾再帰からの書換えでなければ、結局自分で管理するスタックにデータを積むため、労が多いわりに益が少ないこともある。キューを実装に使うこともあるが、それは速度の問題などよりは、縦ではなく横に探索したい(幅優先探索をしたい)といった理由による。