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

Download Report