powerpoint プレゼンテーションnakano/al/al_note1.pdf分割統治法の3ステップ...
Post on 29-May-2020
2 Views
Preview:
TRANSCRIPT
アルゴリズムI
中野
Note 1
2020.4.23実施
2020.4.06作成
分割統治法
多くの有用なアルゴリズムは再帰的な構造をもっている。
すなわち、与えられた問題を、
その問題に関連した幾つかの部分問題を解くことによって解く。
このようなアルゴリズムを、分割統治法と呼ぶ。
(問題はサイズが小さいほうが簡単に解けることが多いこと
に注意。)
分割統治法の3ステップ
分割統治法は次の3ステップからなる。
(分割) 与えられた大きなサイズの問題を、幾つかの(少し小さな)部分問題に分割する。
(統治) これらの部分問題のそれぞれを再帰的に解く。
(結合) 求められた部分問題の解から、元の問題の解を求める。
分割が高速にできることと、
部分問題の解から元の問題の解が高速に求められることが必要。
解右 解左解
分割統治法（再帰アルゴリズム）
分割統治法は一般に下記のように再帰呼び出しを使って書ける。
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,… に分割する
(Conquer)
y1 = Divide-and-Conquer(x1)
y2 = Divide-and-Conquer(x2)
…
yk= Divide-and-Conquer(x2)
(Combine)y1, y2, …から xの解yを作る
return y
分割統治法の例
マージソート, 線型時間( O(n)時間) で中央値を求めるアルゴリズム, 2分探索などは分割統治法である。
他にも膨大な数のアルゴリズムがある。
(Convex Hull, Voronoi diagram, etc.)
多くのアルゴリズムが分割統治法を用いている。
分割統治法はTop Down的な手法である。
(これに対して、動的計画法は Bottom Up的である。)
計算時間 O記法 （オーダー記法）
Insertion-Sort(A)
for j=2 to n
begin
key=A[j]
i=j-1
while i>0 and A[i] > key
begin
A[i+1] = A[i]
i = i-1
end
A[i+1] = key
end
3 6 8 11 19 7
123
7が割り込むところを探す
7より大の数字は順に後にずらす
1番からj-1番までソート済みのときj番までソートずみにする
計算時間 O記法 （つづき）
Insertion-Sort(A)
for j=2 to n n-1回繰り返し
begin
key=A[j] 1回
i=j-1 2回
while i>0 and A[i] > key 高々n回繰り返し
begin
A[i+1] = A[i] 2回
i = i-1 2回
end
A[i+1] = key 2 回
end
(n-1) (3+4n+2)=4n2 – n -2≦ 4n2
O(n2)
マージソート
Merge-Sort(A,p,r) %配列A のうち、A[p..r]の部分の要素をソートする
if p < r then %まだA[p..r]に要素が２個以上あれば（ソート中）
begin
(Divide) %2つの部分配列 A[p..q] と A[q+1..r] に分割
q ← ( (p+r)/2 を切捨てた整数値 )
(Conquer)
Merge-Sort(A,p,q) %前半を再帰的にソート
Merge-Sort(A,q+1,r) %後半を題記的にソート
(Combine)
Merge(A,p,q,r) %マージして全体のソートを完了
end2 5 7 10 13 16 20 34….4 8 9 11 26 28 32 ….
マージソートの計算時間
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は略してもよい。)
T(n) = 2 T(n/2) + O(n) の解き方
T(n) ≦ 2 T(n/2) ＋ c n
≦ 2（……………………）＋ cn カッコの中は？
T(n/2) ≦ 2 T(n/4) + c n/2
T(n) = 2 T(n/2) + O(n) の解き方
T(n) ≦ 2 T(n/2) ＋ cn
≦ 2（2 T(n/4) + c n/2 ）＋ cn カッコの中は？
T(n/2) ≦ 2 T(n/4) + c n/2
T(n) = 2 T(n/2) + O(n) の解き方
T(n) ≦ 2 T(n/2) ＋ cn
≦ 2（2 T(n/4) + c n/2 ）＋ cn カッコの中は？
T(n/2) ≦ 2 T(n/4) + c n/2
≦ 2（2 (.........) + c n/2 ）＋ cn カッコの中は？
T(n/4) ≦ 2 T(n/8) + c n/4
T(n) = 2 T(n/2) + O(n) の解き方
T(n) ≦ 2 T(n/2) ＋ cn <=この式はいろいろなｎで成立！
≦ 2（2 T(n/4) + c n/2 ）＋ cn カッコの中は？
T(n/2) ≦ 2 T(n/4) + c n/2
≦ 2（2 (.........) + c n/2 ）＋ cn カッコの中は？
T(n/4) ≦ 2 T(n/8) + c n/4
≦ 2（2 (2 T(n/8) + c n/4) + c n/2 ）＋ cn
= 23 T(n/23) + 3cn
T(n) = 2 T(n/2) + O(n) の解き方
T(n) ≦ 2 T(n/2) ＋ cn <=この式はいろいろなｎで成立！
≦ 2（2 T(n/4) + c n/2 ）＋ cn≦ 2（2 (2 T(n/8) + c n/4) + c n/2 ）＋ cn
= 23 T(n/23) + 3cn
…(log n回 展開）
= 2 log n T(n/2 log n) + cn log n
= n T(1) + cn log n x = 2 log n
log x = log n log 2
log x = log n
x = n
O( n log n)
クイックソート
pivot(軸) 前半に74以下の数字を集める
後半に74より大きな数字を集める
74
クイックソート
pivot(軸) 前半に54以下の数字を集める
後半に54より大きな数字を集める
54 22 18 72
大なのに前のほうにある
629135
小なのに後のほうにある
クイックソート
pivot(軸) 前半に54以下の数字を集める
後半に54より大きな数字を集める
54 22 18 72
大なのに前のほうにある
629135
小なのに後のほうにある
35 72
交換
クイックソート
pivot(軸) 前半に54以下の数字を集める
後半に54より大きな数字を集める
54 22 18 72
大なのに前のほうにある
629135
小なのに後のほうにある
35 7211 85 895814
クイックソート
pivot(軸) 前半に54以下の数字を集める
後半に54より大きな数字を集める
54 22 18 72
大なのに前のほうにある
629135
小なのに後のほうにある
35 72
交換
11 85 895814
14 85
クイックソート
pivot(軸) 前半に54以下の数字を集める
後半に54より大きな数字を集める
54 22 18 72 629135
35 7211 85 895814
14 85
31 49
完了
あとは、前半を（再帰的に）ソートする後半を（再帰的に）ソートする
マージソートの計算時間
T(n) = ???? (分割の、しかたは一般にはわからない!)
もし、必ず 1個とそれ以外に分割されるとすると （最悪の場合）T(n) = T(n-1) + T(1) + O(n)T(n) ≦ T(n-1) + c1 + c2n
≦ T(n-2) + c1 + c2(n-1) + c1 + c2n= T(n-2) + 2c1 + c2(n + (n-1))≦ T(n-3) + 3c1 + c2(n + (n-1) + (n-2))….≦ T(1 ) + (n-1)c1 + c2n(n-1)/2 O(n2)時間アルゴリズム
The closest pair(最近接ペア）
The closest pair 素朴なアルゴリズム
全ペアの距離をチェック
ans = ∞for i = 1 to n-1
for j = i+1 to nif ans > d(vi , vj)
ans = d(vi , vj)return(ans)
O(n2)時間
n 103 106 109
log n 10 20 30
アルゴリズムの改良（分割統治法）
左右の問題に分ける
左の問題の解を求める ansl
右の問題の解を求める ansr
小さいほうを出力する
だけではダメ！
アルゴリズムの改良（分割統治法）
左右の問題に分ける
左の問題の解を求める ansl
右の問題の解を求める ansr
小さいほうdを出力する
だけではダメ！
左右の境付近の点のペアを
チェックする
アルゴリズムの改良（分割統治法）
左右の問題に分ける
左の問題の解を求める ansl
右の問題の解を求める ansr
小さいほうdを出力する
だけではダメ！
左右の境付近の点のペアを
チェックする
アルゴリズムの改良（分割統治法）
左右の問題に分ける
左の問題の解を求める ansl
右の問題の解を求める ansr
小さいほうdを出力する
だけではダメ！
左右の境付近の点のペアを
チェックする
アルゴリズムの改良（分割統治法）
左右の問題に分ける 境界付近の左の各点につき
チェックすべき
境界付近の右の点は高々6個
よって高々6nペアをチェックすればよい
あらかじめy座標でソートしておけば O(n)時間で計算できます
T(n) ≦ 2 T(n/2) + cn
O( n log n) 時間
理解確認クイズ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) を解け。
(6) T(n) = 2 T(n/2) + O(n log n) を解け。
(7) T(n) ≦ 4 T(n/2) + c' n を解け。
(7) T(n) ≦ 4 T(n/2) + c' n を解け。
(1) T(n) = 2 T(n/2) + O(n) の解き方
T(n) ≦ 2 T(n/2) ＋ cn
≦ 2（2 T(n/22) + c n/2 ）＋ cn
= 22 T(n/22) + 2cn
≦ 22 (2 T(n/23) + c n/22）＋ 2cn
= 23 T(n/23) + 3cn
…(log n回 展開）
= 2 log n T(n/2 log n) + cn log n
= n T(1) + cn log n
x = 2 log n
log x = log n log 2
log x = log n
x = nO( n log n)
(2) T(n) = 2 T(n/2) + O(1) の解き方
T(n) ≦ 2 T(n/2) ＋ c
≦ 2（2 T(n/4) + c ）＋ c
= 22 T(n/22) + 3c
≦ 22 (2 T(n/23) + c ）＋ 3c
= 23 T(n/23) + 7c
…(log n回 展開）
= 2 log n T(n/2 log n) + c(1+2+4+…+2(log n-1))
≦ n T(1) + cn
x = 2 log n
log x = log n log 2
log x = log n
x = nO( n )
12
48
(3) T(n) = 2 T(n/2) + O(n2) の解き方
T(n) ≦ 2 T(n/2) ＋ cn2
≦ 2（2 T(n/22) + c (n/2)2 ）＋ cn2
= 22 T(n/22) + cn2/2 +cn2
≦ 22 ( 2 T(n/23) + c (n/22)2 )＋ (1/2 + 1)cn2
= 23 T(n/23) + (1/22+1/2+1)cn2
…(log n回 展開）
≦ 2 log n T(n/2 log n) + 2cn2
= n T(1) + cn2
x = 2 log n
log x = log n log 2
log x = log n
x = nO( n2)
1/81/4
1/21
(3) T(n) = 2 T(n/2) + O(n3) の解き方
T(n) ≦ 2 T(n/2) ＋ cn3
≦ 2（2 T(n/22) + c (n/2)3 ）＋ cn3
= 22 T(n/22) + cn3/22 +cn3
≦ 22 ( 2 T(n/23) + c (n/22)3 )＋ (1/22 + 1)cn3
= 23 T(n/23) + (1/24+1/22+1)cn3
…(log n回 展開）
≦ 2 log n T(n/2 log n) + 2cn3
= n T(1) + cn3
x = 2 log n
log x = log n log 2
log x = log n
x = nO( n3)
1/161/4
1/21
top related