分割統治法

この項目では、アルゴリズムについて説明しています。政治、歴史分野での分割統治については「分割統治」をご覧ください。

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

擬似コード

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

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

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

その他

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

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

参考文献

• 数値線形代数における分割統治法について
  • 桑島豊, & 重原孝臣. (2005). 実対称三重対角固有値問題の分割統治法の拡張 (行列・固有値問題における線形計算アルゴリズムとその応用). 日本応用数理学会論文誌, 15(2), 89-115.
  • 桑島豊, & 重原孝臣. (2006). 実対称三重対角固有値問題に対する多分割の分割統治法の改良 (理論, 行列・固有値問題の解法とその応用, 平成 18 年研究部会連合発表会). 日本応用数理学会論文誌, 16(4), 453-480.
  • 廣田悠輔, & 今村俊幸. (2015). 帯行列の一般化固有値問題向け分割統治法. 情報処理学会論文誌コンピューティングシステム (ACS), 8(4), 78-87.
  • Elsner, L., Fasse, A., & Langmann, E. (1997). A divide-and-conquer method for the tridiagonal generalized eigenvalue problem. en:Journal of computational and applied mathematics, 86(1), 141-148.
  • Kwak, D. Y., & Kim, J. (2015). A generalization of the divide and conquer algorithm for the symmetric tridiagonal eigenproblem. arXiv preprint arXiv:1506.08517.
  • Tisseur, F., & Dongarra, J. (1999). A parallel divide and conquer algorithm for the symmetric eigenvalue problem on distributed memory architectures. en:SIAM Journal on Scientific Computing, 20(6), 2223-2236.
  • Bai, Z., Demmel, J., & Gu, M. (1997). An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems. en:Numerische Mathematik, 76(3), 279-308.
• 因数分解における分割統治法について
  • 園田信吾, 櫻井鉄也, 杉浦洋, & 鳥居達生. (1991). 分割統治法による多項式の数値的因数分解. 日本応用数理学会論文誌, 1(4), 277-290.
• 計算幾何学における分割統治法について
  • 浅野孝夫. (1984). 計算幾何学とその応用. 情報処理, 25(3).
• 並列計算における分割統治法について
  • 中島大輔, 藤本典幸, & 萩原兼一. (2000). 分割統治法アルゴリズムの効率的な並列化手法とそのコンパイラの実装. 情報処理学会研究報告アルゴリズム (AL), 2000(5 (1999-AL-071)), 25-32.