d - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第10回
最短路問題とダイクストラ法
• 有向グラフ G = (V, E) を考える
– V: 節点集合, 節点数 n
– E: 枝集合, 枝数 m
• グラフ G の各枝 (i,j)  E は長さ aij を持つ
• ある節点 s  V から別の節点 t  V への路の中で，
最も長さの短いものを見つける問題を最短路問題
15
という
2
4
50
30
20
10
1
5
80
3
15
2
• 下のネットワークで節点 1 を s, 節点 5 を t とすると，
s から t へは 1245, 1235,1345,
12345,135 の5つの路がある
• 路の長さはそれぞれ 95, 85, 120, 110, 95 なので，
最短路は 1235 である
• 大規模なネットワークでは全ての路を数え上げる
方法は実用的ではない
15
2
50
4
30
20
10
1
5
80
3
15
3
最適性の原理
• 節点 s から t への最短路 P が得られているとする
• 路 P に含まれる節点を1つ任意に選び, r とする
• 路 P は s から r までの部分 P1 と， r から t への
部分 P2 に分割できる．このとき，P1 は s から r へ
の最短路で，P2 は r から t への最短路となる
– もし P1 より短い s から r への路 P1’が存在するなら，
P1’と P2 をつないだ路は P2 より短くなる
• このような性質を最適性の原理と呼ぶ
P1
P
r
2
s
P1’
t
4
• ある節点 s からネットワークの他の全節点への最
短路を求める問題を考える
• ダイクストラ法は，枝の長さに関する非負条件
aij  0 ((i,j)  E) の仮定の下で，節点 s から各節
点 i  V への最短路の長さの上限値 d(i) を更新し
ていく反復アルゴリズム
• 計算の途中では，d(i) の値が s から i への真の最
短路の長さに等しいことがわかっている節点が存
在する．そのような節点の集合を S で表す
• S は S の補集合 V  S を表す
5
ダイクストラ (Dijkstra) 法
(0) S := , S := V, d(s) := 0, d(i) :=  (i  V  {s})
とおく
(1) S = V なら計算終了．そうでないなら，
d (v)  min d (i) | i  S  である節点 v  S を選ぶ
(2) S : S  {v}, S : S  {v} とし，(v,j) E かつ j  S
であるような全ての枝 (v,j) に対して
d(j) > d(v) + avj ならば d(j) = d(v) + avj, p(j) := v
とする．ステップ (1) に戻る
p(i) は，s から i までの最短路において i の直前に
6
位置する節点を示すために用いられる
[初期化]
(0) S   , S  {1,2,3,4,5}
50
1
d(1)=0
d(2)=
2
20
80
d(4)=
4
15
30
10
3
d(3)=
d(5)=
5
15
7
[反復1]
(1) S  {1,2,3,4,5}
min d (i) | i  S   0 より v = 1
(2) S  {1}, S  {2,3,4,5}
d(2) =  > d(1) + a12 =50 より d(2) = 50, p(2) = 1
d(3) =  > d(1) + a13 =80 より d(3) = 80, p(3) = 1
50
1
d(1)=0
d(2)=50
2
20
d(4)=
4
15
30
10
5
80
3
d(3)=80
d(5)=
15
8
[反復2]
(1) S  {2,3,4,5}
min d (i) | i  S   50 より v = 2
(2) S  {1,2}, S  {3,4,5}
d(3) = 80 > d(2) + a23 =70 より d(3) = 70, p(3) = 2
d(4) =  > d(2) + a24 =65 より d(4) = 65, p(4) = 2
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=
15
9
[反復3]
(1) S  {3,4,5}
min d (i) | i  S   65 より v = 4
(2) S  {1,2,4}, S  {3,5}
d(5) =  > d(4) + a45 =95 より d(5) = 95, p(5) = 4
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=95
15
10
[反復4]
(1) S  {3,5}
min d (i) | i  S   70 より v = 3
(2) S  {1,2,3,4}, S  {5}
d(5) = 95 > d(3) + a35 =85 より d(5) = 85, p(5) = 3
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
11
[反復5]
(1) S  {5}
自動的に v = 5
(2) S  {1,2,3,4,5}, S  
[反復6]
(1) S = V なので終了
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
12
• アルゴリズムが終了したときの d(i) は，節点 1 から
i への最短路の長さを与えている
• 枝の集合 {(p(i),i)} が各節点への最短路を表す
これを最短路木と呼ぶ
50
1
d(1)=0
d(2)=50
2
20
80
d(4)=65
4
15
30
10
3
d(3)=70
5 d(5)=85
15
13
アルゴリズムの正当性の証明
• ダイクストラ法で，S は出発点 s からの最短路の
長さがわかっている節点の集合であることを確認
• 以下のことを帰納法で示す
– 全ての i に対し, d(i) = [S に含まれる節点のみを経由
して s から i に至る最短路の長さ]
(3.3)
(S に含まれる節点のみを経由するのでは到達できな
い場合は d(i) = )
– i  S ならば，d(i) = [s から i への最短路の長さ]
14
• [反復1] 終了後 S = {s}, d(s) = 0
• S の点 s では，s から s への最短距離は 0 で，d(s)
と等しい
• Sの点から1本の枝で到達できる S の点(2 と 3)では
d(i) = [S に含まれる節点のみを経由して s から i
に至る最短路の長さ] が成り立つ
• それ以外の点では d(i) =  で，命題は成立
50
1
d(1)=0
d(2)=50
2
20
d(4)=
4
15
30
10
5
80
3
d(3)=80
d(5)=
15
15
• 帰納法の仮定：ある反復に入った時点で命題成立
• ステップ(1)で v  S が選ばれたときに，v に対し
d(v) = [S に含まれる節点のみを経由して s から v に至る
最短路の長さ]
= [s から v への最短路の長さ]
(3.4)
それ以外の点に対して (3.3) が成り立つことを示す
• (3.4) を背理法で示す．sから v への最短路をP*とし，
その長さが d(v) と異なるとする
• アルゴリズムの構成法より，各節点 i に対し，d(i)
は s から i へのある路の長さを表しているので，
上の仮定は d(v) > [路 P* の長さ] を意味する
16
• v  S なので，(3.3) より，s から v への真の最短路
P* は，途中で S の点を少なくとも1つ経由する
• P* において初めて現れる S の点を u とすると，P*
*
*
は P1 と P2 に分解できる
• 最適性の原理より， P1* は s から u への最短路
• P1* は S の点のみを経由しているので，(3.3) より
*
d(u) = [路 P1 の長さ] が言える
S
S
p(v)
v
P2*
s
u
P1*
17
• 各枝の長さは非負なので，
*
[路 P* の長さ]  [路 P1 の長さ]
• よって，d(v) > d(u)
• ところが，d (v)  min d (i) | i  S  と u  S より
d(v)  d(u) となり，矛盾
• よって，d(v)は s から v への最短路の長さに等しい
• (3.3) より，その路は S の節点のみを経由するので，
S
S
(3.4) が成り立つ
p(v)
v
P2*
s
u
P1*
18
•
•
•
反復が終了した時点で (3.3) が保たれていること
を示す
反復終了時の S を S   S  {v} と書く
アルゴリズムのステップ(2) を実行したとき
+ に含まれる節点のみを経由して
[S
j  S  d ( j) 
s から j に至る最短路の長さ]

•
を示す
S+ に含まれる節点のみを経由して s から j に至
る最短路は次の3つの場合が考えられる
(a) v を経由しない，つまり S の節点のみを経由
(b) j に到達する直前に v を経由
(c) v を経由し，その後さらに S の節点をいくつか通って
19
j に到達
• (c) はありえない．なぜなら，そのような路が最短路
の場合，j の直前の節点を k とすると，最適性の原
理より，その路の k までの部分は sから kの最短路
• k はそれ以前の反復で S に入っているので，S の
節点のみを経由する s から k への最短路が存在
するはず
• よって，s から j への最短路は(a) か (b) のどちらか
• ステップ(2)で，d(j) > d(v) + avj ならば d(j) を
d(v) + avj で置き換えるが，これは (a) よりも(b)の方
が路が短いときに最短路を置き換えることに対応
• 以上より
+ に含まれる節点のみを経由して

[S
j  S  d ( j) 
20
s から j に至る最短路の長さ]
• 次の反復に入ったときも命題が成り立つことが示さ
れた
• 各反復が終了するたびに， S のどれか1つの節点
が S に入るので，アルゴリズムの反復の回数は
節点数 n に等しい
• ステップ(1) の計算量は各反復で O(log n)，
全体で O(n log n)
• ステップ(2) では，ネットワークの各枝はアルゴリズ
ムを通して高々1回だけ処理されるのでステップ(2)
の計算量は全体で O(m log n) (m: 枝数)
• 以上より，ダイクストラ法の計算量は O(m log n)
21
• d の更新を挿入と削除ではなく，フィボナッチヒープ
のdecrease_keyで行うと，総計算量は
O(m + n log n)
22
最小木問題
• 節点集合 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
を全域木の長さと定義する
23
• 長さ最小の全域木を求める問題
貪欲 (greedy) アルゴリズム
• アルゴリズムの各ステップで，その時点で最善と
思われる選択を常に行うアルゴリズム
• 局所的に最善な選択が大局的に最善な解を導く
場合には最適解を与える
• 貪欲アルゴリズムで解ける問題は比較的簡単な
問題といえる
24
成長法による最適全域木の構成
• 「繰り返しの各ステップの直前で，A はある最小全
域木の部分集合」というループ不変式を維持
• 安全な辺=それを加えてもループ不変式を満たす
A := 
while A は最小全域木ではない
A に対して安全な辺 (u,v) を求める
A := A  {(u,v)}
return A
25
定義
• 無向グラフ G = (V, E) のカット (S, VS) とは，
V の分割
• 辺 (u,v)  E の一方の端点が S にあり，他方が
VS にあるとき，(u,v) はカット (S, VS) と交差す
るという
• 辺集合 A に属するどの辺もカットと交差しないと
き，このカットは A を侵害しないという
• カットと交差する辺の中で重み最小の辺を
軽い辺 (light edge) という
26
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: 最小全域木の枝の部分集合
27
定理 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’が存在することを示す．
28
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) を加えると新たな
29
全域木 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’ が形成できる．
30
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) は安全である．
31
クラスカル法
•
•
枝を長さの短い順に1つずつ選ぶ
それを前に選んだ枝の集合に付け加えたときに
閉路を生じないならば，その枝を付け加える
(0) グラフ G の枝を短い順に並べ，枝の番号を付け
替える． A = {e1}, k = 2 とおく．
(1) 枝集合 A  {ek} が閉路を含まないならば，
A := A  {ek} とする
(2) A が G の全域木になっていれば計算終了．
さもなければ k := k + 1 としてステップ(1)へ戻る
32
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
33
• クラスカル法の計算途中では，枝集合 T は一般に
複数の木の集まりになっている．このような集合を
森と呼ぶ．
• どの枝を付け加えても閉路ができてしまうような森
を，全域森と呼ぶ．
• クラスカル法の正当性を背理法で証明する．
• 得られた全域木を T  el1 , el2 , , eln1 とし，枝は
el1 , el2 ,  , eln1 の順に付け加えられたとする．
• al1  al2    aln1が成り立つ
• T より長さの短い全域木 T *  eq1 , eq2 , , eqn1
が別に存在したとする．
aq1  aq2    aqn1 とする
34




• 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 は連結とは限らない．
35
e ,, e 
~
は部分グラフ G の
• 命題：枝集合
l
l
全域森である．
• 証明：枝集合 el , , el  に枝を付け加える段階で，
eq1 ,  , eqr ではなくそれより長い el が選ばれている
ということは， eq1 ,  , eqr のどれを追加しても閉路が
できることを意味する．よって証明された．
~
• 枝集合 el , , el  が G の全域森であるため，
~
G の任意の森は r 本以上の枝を含まない
• 一方， eq1 ,  , eqr は G に対する全域木 T* の枝
~
の一部であり， G でも森になっている．しかしその
枝数は r であるため，矛盾．
• 以上より，クラスカル法で得られた T は最小木．36
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
37
アルゴリズムの効率的な実現
• 以下の操作を効率的に実現する必要がある
枝集合 A  {ek} が閉路を含まないならば，
A := A  {ek} とする
• ek = (u,v) の両端点 u, v が A の異なる連結成分
に属している ⇔ A  {ek} は閉路を含まない
• 「互いに素な集合のためのデータ構造」を用いる
38
互いに素な集合のためのデータ構造
• 互いに素な動的集合の集合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 以下
39
連結リストによる表現
• 各集合を連結リストで表現する
• リストの先頭のオブジェクトがその集合の
代表元の役割をする
• 各オブジェクトは集合の要素，次のオブジェク
トへのポインタ，代表元に戻るポインタを持つ
• 各リストは代表元へのポインタ head とリスト
の最後の要素へのポインタ tail を持つ
head(L)
tail(L)
9
16
4
40
• 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)
41
• このアルゴリズムはどこが悪いのか
– 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) である．
42
証明：n 個の各要素に対し，代表元へのポインタが
更新される回数の上界を求める．
ある要素 x において，その代表元ポインタが更新
されるとき，x は常に小さい方の集合に属している．
従って，最初に x の代表元ポインタが更新された
時，得られる集合のサイズは2以上．
代表元ポインタが k 回更新された後に得られる
集合は，少なくとも 2k 個の要素を持っている．
要素は n 個しかないので，k  log n.
43
(続き)
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
44
クラスカルのアルゴリズム
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
45
クラスカル法の計算量
•
•
•
•
•
•
辺のソート: 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)
46
プリム (Prim) のアルゴリズム
• 最小全域木の部分集合 A を常に連結にしながら
更新していくアルゴリズム
• 初期状態は A はある任意の点
• カットは (A, VA) になっている
• ダイクストラ法に似ている
47
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)
48
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
49
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
50
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
51
• アルゴリズムの各段階で，d[u] はカット (A, VA) と
交差する辺 (v,u) の中で最短のものの長さを表す
– (v,u) は軽い辺
• d[u] が最小になる u を A に加える
52
プリム法の計算量
• 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)
53

Download Report