1. 分割統治法(Divide and Conquer)

1.1 分割統治法

多くの有用なアルゴリズムは再帰的な構造をもっている。すなわち、
与えられた問題を、その問題に関連した幾つかの部分問題を解くことによって解く。
このようなアルゴリズムを、分割統治法と呼ぶ。
(問題は、サイズが小さいほうが簡単に解けることが多いことに注意。)

分割統治法は次の3ステップからなる。
(分割 Divide) 与えられた大きなサイズの問題を、幾つかの(サイズが少し小さな)部分問題に分割する。
(統治 Conquer) これらの部分問題のそれぞれを再帰的に解く。
(結合 Combine) 求められた部分問題の解から、元の問題の解を求める。

分割が高速にできることと、元の問題の解が部分問題の解から高速に求められることが必要である。

分割統治法は一般に下記のように再帰よびだしを使って書ける。

問題を2つに分割する場合

     
function Divide-and-Conquer(x)
	if x は十分小さい または 単純である 
        then 簡単な方法で解き return
	(Divide)
	x を 2個の部分問題 x1, x2 に分割する
	(Conquer)
	y1 = Divide-and-Conquer(x1)
	y2 = Divide-and-Conquer(x2)
	(Combine)
	y1と y2 から xの解yを作る
	return y
問題をk個に分割する場合
     
function Divide-and-Conquer(x)
	if x は十分小さい または 単純である 
        then 簡単な方法で解き return
	(Divide)
	x を k個の部分問題 x1, x2, ..., xk に分割する
	(Conquer)
	for i = 1 to k do
		yi = Divide-and-Conquer(xi)
	(Combine)
	y1, y2, ..., yk から、 xの解yを作る
	return y
マージソート, 線型時間( O(n)時間) で中央値を求めるアルゴリズム, 2分探索などは分割統治法である。 他にも膨大な数のアルゴリズムがある。(Convex Hull, Voronoi diagram, etc.) 多くのアルゴリズムがこの手法を用いている。 分割統治法はTop Down的な手法である。 (これに対して、動的計画法は Bottom Up的である。) 1.2 マージソート
     
Merge-Sort(A,p,r)
	if p < r then 
	begin
	(Divide)
	   q ←  ( (p+r)/2 を切捨てた整数値 )
	(Conquer)
	   Merge-Sort(A,p,q)
	   Merge-Sort(A,q+1,r)
	(Combine)
	   Merge(A,p,q,r)
	end
サブルーチン Merge-Sort(A,p,r) は、 配列A のうち、A[p..r]の部分の要素をソートする。 もし、 p ≧ r ならば、A[p..r] は、高々1つの要素しか持たないので、ソート済みである。 (よって、何もしない。) そうでないときは、qを計算し、A[p..r] を2つの部分配列 A[p..q] と A[q+1..r] に分割する。 2つの部分配列 A[p..q] と A[q+1..r] をそれぞれ(再帰的に)ソートし、 最後に(Combine)によって A[p..r]のソートを得る。 n個の要素からなる配列 A[1..n] をソートするには、Merge-Sort(A,1,n)を実行すればよい。 n個の要素からなる配列をソートする時間をT(n)とする。 if n>1 then T(n) = 2 T(n/2) + O(n) となる。 if n=1 then T(1) = c となる。 これを解くと T(n)は? 注意 十分小さなnに対しては、常に、T(n) = c となるので、 これを略してもよいことにする。(つまり上の例では T(1)=cは略してもよい。) 1.3 クイックソート T(n) = ???? (分割の、しかたは一般にはわからない!) (もし、必ず 1個とそれ以外に分割されるとすると ) T(n) = T(n-1) + T(1) + O(n) これを解くと T(n) = O(n2)となる。 1.4 The closest pair 平面上にn 個の点があり、どの2点も座標が異なるとする。 これらの点のうち、最も距離が短い点のペアを探す問題を考えよう。 (点が飛行機ならば、このようなペアは、衝突の可能性がある要注意ペアとなる。) 素朴な方法 それぞれのペア(nC2個ある)の間の距離を、すべて計算し、 距離が最小値となるペアを探す。 これは、O(n2) 時間のアルゴリズムである。 分割統治法 下に説明するように、 T(n) = 2 T(n/2) + O(n) となる。 すなわち、サイズが半分の問題を2つ解き、O(n)かけて統治する。 この再帰式を解くと、O(n log n) 時間のアルゴリズムであることがわかる。 まず、n個の点の集合をPとする。 P中の点をx座標でソートし、配列 X に格納する。 P中の点をy座標でソートし、配列 Y に格納する。 もし、点の個数|P|が3個以下ならば、それぞれのペアの間の距離を、すべて計算し 距離が最小値となるペアを探す。 もし、点の個数|P|が3個より多ければ、下記のようにする。 (Divide) P を、ほぼ半分の個数の、2つの集合に分割する。 境界のx座標を xpとする。 x座標が小さい方の(左)半分を PLとする。 x座標が大きい方の(右)半分を PRとする。 (ここでソートは必要ありません。配列X を前半と後半に区切るだけです。) PL中の点をy座標でソートしたものYLを作成する。 PR中の点をy座標でソートしたものYRを作成する。 (配列Y中の各点を、x座標により、YLとYRのいずれかに ふりわけて順に入れる。 得られたYLとYRは、それぞれy座標でソートされている。 これらの作成にはO(n)時間しかかからない。) (Conquer) PL の closest pair を(再帰的に)求める。 2点aL,bL間の距離 dLが最小であったとする。 PR の closest pair を(再帰的に)求める。 2点aR,bR間の距離 dRが最小であったとする。 (Combine) Pの closest pair は、次の3通りのうちの、いずれかである。 (1) PL の closest pair (2) PR の closest pair (3) PL 中の1点aと、PR 中の1点bからなる closest pair (1)と(2)は、すでに求められている。 (3)は下記のようにしてO(n)時間で(高速に)求めることができる。 (3)は、ペアの間の距離をすべて計算する必要はないのがミソである。 (全部ではなく、ある条件を満たすペアの間の距離のみ計算すればよい。) d = min{ dL, dR} とする。 (3)の2点a,bが P のclosest pairとなるためには、 2点a,bは、境界の座標 xpから、高々dだけ離れた領域内にあるはずである。 また、2点の垂直方向の差も、高々dしか離れていないはずである。 ここで、aのy座標 < bのy座標と仮定しよう。 このとき、2点 a, b が closest pair となるならば、この2点は 幅2d、高さd の領域内にあるはずである。 しかし、(1)と(2)の答えが dLと dRであることから、 この領域には、高々6個の点しか存在しない。 aの候補は、PLの中にあり、かつ、 境界から高々dだけ離れた領域内にあるもののみである。 このaに対し、bの候補は、PRの中にあり、かつ、 境界から高々dだけ離れた領域内にあり、かつ、 y座標は、aよりも高々dだけ大きいもののみである。 すなわち、各点aに対し、点bの候補は高々4個である。 すなわち、(3)のclosest pairは O(4n) = O(n)時間で求めることができる。 1.5 理解確認クイズ T(1)=cは 略。nは2のべき乗としてよい。 (1) T(n) = 2 T(n/2) + O(n) を解け。 (2) T(n) = T(n/2) + O(1) を解け。 (3) T(n) = 2 T(n/2) + O(n2) を解け。 (4) T(n) = 2 T(n/2) + O(n3) を解け。 (5) T(n) = 2 T(n/2) + O(n4) を解け。 ( T(n) ≦ 2 T(n/2) + c' n4 を解け。) (6) T(n) = 2 T(n/2) + O(n log n) を解け。 T(n) ≦ 2 T(n/2) + c' n log n ≦ 2 ( 2 T(n/4) + c' (n/2) log (n/2) ) + c' n log n ≦ 4 T(n/4) + c' n log n + c' n log n ≦ 4 ( 2 T(n/8) + c' (n/4) log (n/4) ) + 2 c' n log n ≦ 8 T(n/8) + c' n log n + 2 c' n log n ≦ 8 T(n/8) + 3 c' n log n = ... ≦ nT(1) + c' n log 2 n すなわち T(n) = O(n log 2 n) となる。 (7) T(n) ≦ 4 T(n/2) + c' n を解け。 (以下上級者向け) (8) T(n) ≦ 4 T(n/2) + c' n2 を解け。 (9) T(n) ≦ 4 T(n/2) + c' n3 を解け。 (10) T(n) = 2 T(n/2 + 17) + O(n) を解け。 (11) T(n) = T(n/3) + T(2n/3) + O(n) を解け。 (12) closest pair を求める O(n log n) 時間アルゴリズムの詳細を設計せよ。

     
function Insertion-Sort(A)
for j=2 to n
begin
   key = A[j]
   i   = j-1
   while i>0 かつ A[i] > key
   begin             {keyがわりこむ場所を探す}
      A[i+1] = A[i]
      i = i-1
   end
   A[i+1] = key
end   
closest pairのアルゴリズムは
Are You Smart Enough to Work at Google?
Poundstone著2012年 のp247にも解説があります
日本語版 Googleがほしがるスマート脳のつくり方
パウンドストーン著 2012年 p344
Copyright 2018 by Shin-ichi Nakano