V - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第11回
最小木問題
• 節点集合 V = {1,2,…,n} と枝集合 {e1,e2,…,em}
をもつ連結無向グラフ G = (V,E) に対して，G と
同じ節点集合 V を持ち，E の部分集合 T を枝集合
とするグラフ G’ = (V,T) を考える
• 各節点 i V は少なくとも1つの枝 ej T の端点に
なっているとする
• G’ が閉路を含まない連結グラフ，すなわち木に
なっているならば， G’ を G の全域木という
• 各枝 ei E に長さ ai が与えられているとき，  ai
ei T
を全域木の長さと定義する
2
• 長さ最小の全域木を求める問題
貪欲 (greedy) アルゴリズム
• アルゴリズムの各ステップで，その時点で最善と
思われる選択を常に行うアルゴリズム
• 局所的に最善な選択が大局的に最善な解を導く
場合には最適解を与える
• 貪欲アルゴリズムで解ける問題は比較的簡単な
問題といえる
3
成長法による最適全域木の構成
• 「繰り返しの各ステップの直前で，A はある最小全
域木の部分集合」というループ不変式を維持
• 安全な辺=それを加えてもループ不変式を満たす
A := 
while A は最小全域木ではない
A に対して安全な辺 (u,v) を求める
A := A  {(u,v)}
return A
4
定義
• 無向グラフ G = (V, E) のカット (S, VS) とは，
V の分割
• 辺 (u,v)  E の一方の端点が S にあり，他方が
VS にあるとき，(u,v) はカット (S, VS) と交差す
るという
• 辺集合 A に属するどの辺もカットと交差しないと
き，このカットは A を侵害しないという
• カットと交差する辺の中で重み最小の辺を
軽い辺 (light edge) という
5
4
8
b
7
c
d
9
2
11
a
S
8
VS
i
6
7
h
1
e
14
4
10
g
2
f
カット
軽い枝
A: 最小全域木の枝の部分集合
6
定理 1: グラフ G = (V, E) のある最小全域木に
含まれる E の任意の部分集合を A，A を侵害
しない G の任意のカットを (S, VS)，そのカットと
交差する任意の軽い辺を (u,v) とする．このとき，
辺 (u,v) は A に対して安全である．
証明：A を含む任意の最小全域木 T に対し，
・ T が (u,v) を含む→OK
・ T が (u,v) を含まない→A  {(u,v)} を含む別の
最小全域木 T’が存在することを示す．
7
T の u から v への経路 p 上の辺に (u,v) を加える
と閉路ができる．u と v はカット (S, VS) の反対側
にあるから，経路 p 上にこのカットと交差する T の
辺が少なくとも1つ存在する．
このような辺の1つを (x,y) とする．
カット (S, VS) は A を侵害しないから，A は辺 (x,y)
を含まない．(x,y) は T における u から v への唯一
の経路上にあるから， (x,y) を削除すると T は2つの
成分に分かれる．これに (u,v) を加えると新たな
8
全域木 T’ = T{(x,y)}{(u,v)} ができる．
e
x
u
p
y
v
(u,v) はカットと交差する軽い辺
(u,v) は T における u から v への唯一の経路 p の辺
T から辺 (x,y) を削除し，辺 (u,v) を加えることにより
(u,v) を含む最小全域木 T’ が形成できる．
9
T’ が最小全域木であることを示す．
(u,v) はカットと交差する軽い辺であり，(x,y) もこの
カットと交差するから，w(u,v)  w(x,y) である．
w(T’) = w(T)w(x,y)+w(u,v)  w(T)
となるが，T は最小全域木なので w(T)  w(T’).
従って，T’ も最小全域木である．
(u,v) が A に対する安全な辺であることを示す．
A  T かつ (x,y)  A より，A  T’ である．
従って， A  {(u,v)}  T’ である．
T’は最小全域木なので，(u,v) は安全である．
10
クラスカル法
•
•
枝を長さの短い順に1つずつ選ぶ
それを前に選んだ枝の集合に付け加えたときに
閉路を生じないならば，その枝を付け加える
(0) グラフ G の枝を短い順に並べ，枝の番号を付け
替える． A = {e1}, k = 2 とおく．
(1) 枝集合 A  {ek} が閉路を含まないならば，
A := A  {ek} とする
(2) A が G の全域木になっていれば計算終了．
さもなければ k := k + 1 としてステップ(1)へ戻る
11
3
12
8
3
11
12
9
10
8
11
9
10
15
15
3
12
8
11
9
10
3
15
8
3
11
9
10
12
8
12
15
11
9
10
15
12
• クラスカル法の計算途中では，枝集合 T は一般に
複数の木の集まりになっている．このような集合を
森と呼ぶ．
• どの枝を付け加えても閉路ができてしまうような森
を，全域森と呼ぶ．
• クラスカル法の正当性を背理法で証明する．
• 得られた全域木を T  el1 , el2 , , eln1 とし，枝は
el1 , el2 ,  , eln1 の順に付け加えられたとする．
• al1  al2    aln1が成り立つ
• T より長さの短い全域木 T *  eq1 , eq2 , , eqn1
が別に存在したとする．
aq1  aq2    aqn1 とする
13




• T* の長さは T よりも短いので， aqi  ali となる
i が存在する．
• そのような i の中で最小のものを r とすると
 a q1



a qr 1
 a qr

a l1

 a lr 1


a lr

~
• 枝集合 T  el1 ,, elr1 , eq1 ,, eqr からなる部分
~
グラフ G を考える．
~
ただし， T には枝が重複して含まれている可能性
~
もある．また，一般に G は連結とは限らない．
14
e ,, e 
~
は部分グラフ G の
• 命題：枝集合
l
l
全域森である．
• 証明：枝集合 el , , el  に枝を付け加える段階で，
eq1 ,  , eqr ではなくそれより長い el が選ばれている
ということは， eq1 ,  , eqr のどれを追加しても閉路が
できることを意味する．よって証明された．
~
• 枝集合 el , , el  が G の全域森であるため，
~
G の任意の森は r 本以上の枝を含まない
• 一方， eq1 ,  , eqr は G に対する全域木 T* の枝
~
の一部であり， G でも森になっている．しかしその
枝数は r であるため，矛盾．
• 以上より，クラスカル法で得られた T は最小木．15
r 1
1
r 1
1
r
1

r 1

別証明(カットを用いた証明)
ek = (u,v) の片方の端点 u を含む A の連結成分を
S とすると，A の辺はカットと交差しない，つまり
このカットは A を侵害しない．また，(u,v) はカットと
交差する辺の中で最短，つまり軽い辺である．
8
7
v
4
9
2
11
8
14
4
6
7
1
10
2
u
S
VS
16
アルゴリズムの効率的な実現
• 以下の操作を効率的に実現する必要がある
枝集合 A  {ek} が閉路を含まないならば，
A := A  {ek} とする
• ek = (u,v) の両端点 u, v が A の異なる連結成分
に属している ⇔ A  {ek} は閉路を含まない
• 「互いに素な集合のためのデータ構造」を用いる
17
互いに素な集合のためのデータ構造
• 互いに素な動的集合の集合S={S1, S2,…, Sk}を扱う
• make_set(x):唯一の要素xをもつ新しい集合を作る
– x がすでに別の集合に含まれていてはいけない
• union(x, y): x と y を含む集合 Sx と Sy を合併し，
それらの和集合を作る．元の集合はSから取り除く．
• find_set(x): x を含む集合の代表元へのポインタを
返す
• make_setの回数 n と全操作の総実行回数 m で
評価する．
– unionの回数は n1 以下
18
連結リストによる表現
• 各集合を連結リストで表現する
• リストの先頭のオブジェクトがその集合の
代表元の役割をする
• 各オブジェクトは集合の要素，次のオブジェク
トへのポインタ，代表元に戻るポインタを持つ
• 各リストは代表元へのポインタ head とリスト
の最後の要素へのポインタ tail を持つ
head(L)
tail(L)
9
16
4
19
• make_set(x) と find_set(x) は簡単で O(1) 時間
• union(x,y) は?
• x のリストを y のリストの最後に追加する場合
– x のリストにあった各オブジェクトの代表元への
ポインタを書き換える必要がある
– x のリストの長さに比例する時間がかかる
• (m2) 時間かかる長さ m の操作列が存在
– 初めに n 回の make_set を実行
– 次に n1 回の union を実行 (m = 2n1)
20
• このアルゴリズムはどこが悪いのか
– union(x,y) で常に x を y の末尾に追加しているので，
x が長いと時間がかかる
• x と y の短いほうを長いほうの末尾に追加すれば
計算量を抑えられる?
– 長さ n/2 同士のリストの併合は (n) 時間かかるので
最悪計算量は同じ
• ならし計算量(amortized time complexity)で評価
– m 回の操作全体での計算量で評価する
• 定理: 長さ m の make_set, union, find_set 操作の
列の実行の計算量は，その中の n 回が make_set
のとき，O(m + n log n) である．
21
証明：n 個の各要素に対し，代表元へのポインタが
更新される回数の上界を求める．
ある要素 x において，その代表元ポインタが更新
されるとき，x は常に小さい方の集合に属している．
従って，最初に x の代表元ポインタが更新された
時，得られる集合のサイズは2以上．
代表元ポインタが k 回更新された後に得られる
集合は，少なくとも 2k 個の要素を持っている．
要素は n 個しかないので，k  log n.
22
(続き)
n 個のオブジェクトを更新するのにかかる総時間は
O(n log n).
make_set と find_set 操作は1回あたり O(1),
m 回の操作全体で O(m).
従って，列全体に対する総時間計算量は
O(m + n log n).
15
2
50
4
30
20
10
1
5
80
3
15
23
クラスカルのアルゴリズム
mst_kruskal(G, w)
1. A := 
2. for v V(G)
3.
make_set(v)
4. 重み w の順に E の辺をソートする
5. for (u,v) E (重みの小さい順)
6.
if find_set(u)  find_set(v) then
7.
A := A  {(u,v)}
8.
union(u,v)
9. return A
24
クラスカル法の計算量
•
•
•
•
•
•
辺のソート: O(m log m)
make_set: n 回
find_set: 2m 回
union: n1 回
素な集合の操作全体で O(m + n log n)
m = O(n2) より
クラスカル法の計算量は O(m log n)
25
プリム (Prim) のアルゴリズム
• 最小全域木の部分集合 A を常に連結にしながら
更新していくアルゴリズム
• 初期状態は A はある任意の点
• カットは (A, VA) になっている
• ダイクストラ法に似ている
26
mst_prim(G, w, r)
1. for each u  V(G) d[u] := 
2. d[r] := 0; [r] := NIL
3. Q := V(G); // Q = VA
4. while Q  
5.
u := extract_min(Q)
6.
for each (u,v)  E(G)
7.
if v  Q かつ w(u,v) < d[v] then
8.
[v] := u
9.
d[v] := w(u,v)
27
Q = {1,2,3,4,5}
50
1
d(1)=0
Q = {2,3,4,5}
50
1
d(1)=0
d(2)=
2
d(4)=
4
15
30
20
10
5
80
3
d(3)=
d(2)=50
2
20
15
d(4)=
4
15
30
10
5
80
d(5)=
3
d(3)=80
d(5)=
15
28
Q = {3,4,5}
50
1
d(1)=0
d(4)=15
4
15
30
20
10
5
80
Q = {3,5}
50
1
d(1)=0
d(2)=50
2
3
d(3)=20
d(2)=50
2
20
80
d(5)=
15
d(4)=15
4
15
30
10
3
d(3)=10
5 d(5)=30
15
29
Q = {5}
50
1
d(1)=0
50
30
10
5 d(5)=15
3
d(3)=10
d(2)=50
2
20
80
d(4)=15
4
15
20
80
Q = {}
1
d(1)=0
d(2)=50
2
15
d(4)=10
4
15
30
10
3
d(3)=10
d(5)=15
5
15
30
• アルゴリズムの各段階で，d[u] はカット (A, VA) と
交差する辺 (v,u) の中で最短のものの長さを表す
– (v,u) は軽い辺
• d[u] が最小になる u を A に加える
31
プリム法の計算量
• extract_min: O(n) 回
• d の更新 (heapの挿入削除): O(m) 回
• 総計算量: O(n log n + m log n) = O(m log n)
– クラスカル法と同じ
• d の更新を挿入と削除ではなく，フィボナッチヒープ
のdecrease_keyで行うと，総計算量は
O(m + n log n)
32
9. 線形時間のソーティング
• 今までのソートアルゴリズム
– 入力要素の比較のみに基づく
– 比較ソート (comparison sort) と呼ぶ
– 例：マージソート，ヒープソート，クイックソート
– 計算量：(n lg n)
• この節でのソートアルゴリズム
– 比較以外の演算を用いる
– 例：計数ソート，基数ソート，バケットソート
– 計算量：O(n) (線形時間)
33
9.2 計数ソート (counting sort)
• n 個の各入力要素が 1 から k の範囲の整数で
あると仮定 (k: ある整数)
• k = O(n) のとき，計数ソートは O(n) 時間
• 基本的なアイデア
– 各入力要素 x に対し，x より小さい要素の数を決定
– その要素数から x の出力配列での位置が決まる
– 例： x より小さい数が17個 ⇒ x の出力位置は18
– 複数の要素が同じ値を持つ場合に対応する必要あり
34
計数ソートのプログラム
• A[1..n], B[1..n]: 入出力配列
• C[1..k]: 補助的な配列
void COUNTING_SORT(int *A, int *B, int *C, int n, int k)
{
int i,j;
for (i=1; i<=k; i++) C[i] = 0;
for (j=1; j<=n; j++) C[A[j]] = C[A[j]] + 1;
// C[i] は i に等しい要素の個数を含む
for (i=2; i<=k; i++) C[i] = C[i] + C[i-1];
// C[i] は i 以下の要素の個数を含む
for (j=n; j>=1; j--) {
B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]] - 1;
}
}
35
1 2 3 4 5 6 7 8
A 3 6 4 1 3 4 1 4
1 2 3 4 5 6
C 2 0 2 3 0 1
1 2 3 4 5 6
C 120 2 423 7546 7 87
1 2 3 4 5 6 7 8
B 1 1 3 3 4 4 4 6
for (j=1; j<=n; j++) C[A[j]] = C[A[j]] + 1;
// C[i] は i に等しい要素の個数を含む
for (i=2; i<=k; i++) C[i] = C[i] + C[i-1];
// C[i] は i 以下の要素の個数を含む
for (j=n; j>=1; j--) {
B[C[A[j]]] = A[j]; // A[j]以下がC[A[j]]個
C[A[j]] = C[A[j]] - 1;
}
36
計数ソートの計算時間
•
•
•
•
C の初期化: O(k) 時間
頻度の計算: O(n) 時間
累積頻度の計算: O(k) 時間
出力配列の計算: O(n) 時間
• 全体で O(k + n) 時間
• k = O(n) のとき，全体で O(n) 時間
• 比較ソートの下限 (n lg n) を下回る
37
安定なソート
• 同一の値は入力と出力で同じ順序になる
• 付属データをキーに従ってソートする場合に重要
1 2 3 4 5 6 7 8
A 3 6 4 1 3 4 1 4
B 1 1 3 3 4 4 4 6
38
9.3 基数ソート (radix sort)
• 数の集合をある桁に従って分割する機械がある
• この機械を用いて d 桁の数 n 個をソートしたい
329
457
657
839
436
720
355
329
355
457
436
657
720
839
39
• まず最上位桁でソート (分割) し，それぞれを
再帰的にソートすることを考える
• 大量の部分問題が生成される
• 解：最下位桁からソートする⇒基数ソート
– まず最下位桁に従ってソート
– 次に下から2桁目に従ってソート
– d 桁目まで繰り返す
40
329
457
657
839
436
720
355
720
355
436
457
657
329
839
720
329
436
839
355
457
657
329
355
436
457
657
720
839
基数ソートでは各桁のソートは安定である必要がある
41
基数ソートの擬似コード
RADIX_SORT(A,d)
1. for (i=1; i<=d; i++)
2. 安定ソートを用いて i 桁目に関して配列をソー
ト
実行時間の解析
• 各桁が 1 から k の範囲として計数ソートを使用
• d パスあるので (d(n+k)) 時間
42
• d が定数で k = O(n) ならば，全体で O(n) 時間
• n = 100万個の64ビットの数をソートするとする
• 比較ソートでは1つの数あたりほぼ lg n = 20 回の
操作が必要となる
• 基数ソートでは，これらの数を4桁の216進数と思う
と，4回のパスでソートできる
• 計数ソートを用いる基数ソートはin-placeではない
– メモリが高価な場合はクイックソートなどの方が良い
43
9.4 バケットソート (bucket sort)
• 入力： [0,1) の実数 n 個．一様分布と仮定
• アイデア
– 区間を n 個の同じサイズの部分区間 (バケット) に分割
– n 個の入力をバケットに分配
– 各バケットを独立にソート
0.15
0.51 0.45 0.75 0.80
[0,.2) [.2,.4) [.4,.6) [.6,.8) [.8,1.0)
44
バケットソートの動作
A[1..n]: 入力配列
B[0..n1]: バケット (リストの配列)
BUCKET_SORT(A,n)
1. for (i = 1; i  n; i++)
2.
A[i] をリスト B[nA[i]] に挿入する
3. for (i = 0; i  n1; i++)
4. リスト B[i] を挿入ソートでソートする
5. リスト B[0], B[1],...,B[n1] を順に連接する
45
1
2
3
4
5
6
7
8
9
10
A
.78
.17
.39
.26
.72
.94
.21
.12
.23
.68
.12
B
0
1
2
3
.12
.17
.21
.26
.23
.39
.17
.23
.26
.21
.26
4
5
6
7
.68
.72
.78
.78
8
9
.94
.17 各リストを挿入ソートでソート
.21
.23
.26
.39
.68
.72
.78
.94
46
アルゴリズムの正当性
• A[i] と A[j] が同じバケットに入る場合
– 各バケットは挿入ソートでソートされるのでOK
• A[i] と A[j] が異なるバケットに入る場合
– バケット B[i’], B[j’] (i’ j’)に入るとする
– アルゴリズムの最後で B のリストは結合される
– B[i’] の要素は B[j’] の要素よりも前に現れる
– よって，出力中で A[i] は A[j] よりも前に現れる
– つまり， A[i]  A[j] を示せばよい
47
• A[i]  A[j] と仮定して矛盾を導く．
i  nA[i ]
 nA[ j ]
 j
• となり，i’ j’ に矛盾する
48
実行時間の解析
• 挿入ソート以外の部分は O(n) 時間
• Ni: バケット B[i] に入れられる要素数を表す
確率変数
• バケット B[i] の要素をソートするのに必要な
平均時間 = E[O(Ni2)] = O(E[Ni2])
• 全てのバケット中の要素をソートする時間は
n 1
n 1

2
2 
O(E[ N i ])  O  E[ N i ] 

i 0
 i 0

49
確率変数 Ni の分布
•
•
•
•
•
要素数 = バケット数 = n
ある要素が B[i] に入る確率は p = 1/n
Ni = k となる確率は2項分布 B(k;n,p) に従う
E[Ni] = np = 1, Var[Ni] = np(1p) = 11/n
E[Ni2] = Var[Ni] + E2[Ni] = 21/n = (1)
以上より，挿入ソートに必要な時間は O(n)
バケットソートは線形時間で動作する
50

Download Report