アルゴリズム----五大アルゴリズムの分治法

分治法の設計思想は:1つの直接解決しにくい大きな問題を、いくつかの規模の小さい同じ問題に分割して、それぞれを破壊して、分して治すことです.
1.基本概念
字面上の解釈は「分けて治める」であり、1つの複雑な問題を2つ以上の同じまたは類似のサブ問題に分け、サブ問題をより小さなサブ問題に分ける......最後のサブ問題が簡単に直接解くことができるまで、元の問題の解、すなわちサブ問題の解の合併である.このテクニックは,高速ソート,集計ソートなど,多くの効率的なアルゴリズムの基礎である.
2.適用範囲
分治法で解決できる問題は一般的に以下の特徴を持っている.
1)この問題の規模をある程度縮小すれば容易に解決できる
2)この問題は、最適なサブ構造特性を有するいくつかの小規模な同じ問題に分解することができる.
3)この問題によって分解されたサブ問題の解をその問題の解にまとめることができる.
4)この問題によって分解された各サブ問題は互いに独立しており,すなわちサブ問題間に共通のサブ問題は含まれていない.
各サブ問題が独立していない場合、分治法は多くの不要な仕事をし、共通のサブ問題を繰り返し解く.この場合、分治法が用いられるが、一般的に動的計画法が用いられるのがよい.
3.分治法の手順
分割法には、各階層の再帰に3つのステップがあります.
Step 1分解:原問題をいくつかの規模が小さく、互いに独立し、原問題の形式と同じサブ問題に分解する.
Step 2解決:サブ問題の規模が小さく解決されやすい場合は直接解くが,そうでなければ各サブ問題を再帰的に解く.
Step 3マージ:各サブ問題の解を元の問題の解にマージする.
その一般的なアルゴリズム設計モデルは以下の通りである.
 Divide-and-Conquer(P)

 if |P|≤n0
    then return(ADHOC(P))
     P          P1 ,P2 ,...,Pk
    for i←1 to k
    do yi ←Divide-and-Conquer(Pi) △     Pi
     T ←MERGE(y1,y2,...,yk) △      
    return(T)

そのうち|P|は問題Pの規模を表す.n 0は閾値であり,問題Pの規模がn 0を超えない場合には,問題が直接解かれやすく,これ以上分解を続ける必要がないことを示す.ADHOC(P)は,この分割法における基本的なサブアルゴリズムであり,小規模な問題Pを直接解くために用いられる.したがって,Pの規模がn 0を超えない場合はアルゴリズムADHOC(P)で直接解く.アルゴリズムMERGE(y 1,y 2,...,yk)は、Pのサブ問題P 1,P 2,...,Pkの対応する解y 1,y 2,...,ykはPの解にマージされる.
4.複雑度分析
参照http://blog.sina.com.cn/s/blog_48258fbe0100gcy8.html
5.典型的な問題
(1)二分探索
(2)大整数乗算
(3)Strassen行列乗算
(4)ボードオーバーライド
(5)連結ソート
(6)クイックソート
(7)リニア時間選択
(8)最近接点対問題
(9)サイクルスケジュール
(10)HANOIタワー
参照先:http://c.chinaitlab.com/special/algorithm/Index.html