分割統治法
分割統治法（ぶんかつとうちほう、英: 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.
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
「Divide and conquer algorithm」の例文・使い方・用例・文例
- 私はまず、この点をAmandaに確認します。
- 11月21日にHolyoke Bar and Grillで、Pete Laurenの退職パーティーが開かれることをお知らせします。11 月10 日までにお返事をください。
- 来月のロンドンへの出張のために、飛行機の便を予約して、Southland銀行の近くの宿泊施設を手配してもらえますか。
- 年次監査を行うために、Bradford and Partnersの会計士たちが10 月10 日の午前10 時に当社を訪ねてくる予定です。
- 一般に公開されたことのない、Ruth and Steve Whitmanの個人コレクションの絵画を含む、およそ120 点の作品が展示される。
- Ruth and Steve Whitmanを紹介すること。
- Conteeさんは、昨年Hope and Learnの会長に就任された、受賞歴のあるミュージカル女優さんです。
- Hope and Learnは遠隔地に学校を建設する資金を集める慈善団体です。
- Hope and Learnへの寄付は、この夜会の最後に集めます。
- 気をつけの姿勢で立つ (⇔stand at ease).
- 等位[対等]接続詞 《対等の語句を接続する and, but など》.
- 等位接続詞 《and, but, or, for など; ⇔subordinate conjunction》.
- 連結接続詞 《and など》.
- 【文法】 相関接続詞 《both…and; either…or など》.
- 蒸留酒, 火酒 《brandy, gin, rum, whiskey など》.
- 英国陸軍士官学校 《Berkshire の Sandhurst /sndhɚːst｜‐həːst/ にある》.
- (英国の)運輸省. the Ministry of Education(, Science and Culture) (日本の)文部省.
- 中央裁判所施設 《London の Strand 街にある高等法院の建物》.
- 弱形 《and の /ən/など》.
- 《主に米国で用いられる》 ＝ 《主に英国で用いられる》 the Committee of Ways and Means 歳入委員会.
Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
- Divide-and-conquer algorithmのページへのリンク
