離散数学

Size: px

Start display at page:

Download "離散数学"

えみたかはし
6 years ago
Views:

1 離散数学最小全域木と最大流問題落合秀也

2 今日の内容最小全域木プリムのアルゴリズム最大流問題フォードファルカーソンのアルゴリズム

3 今日の内容最小全域木プリムのアルゴリズム最大流問題フォードファルカーソンのアルゴリズム

4 最小全域木を考える Minimum Spanning Tree Problem ラベル付 ( 重み付 ) グラフ G(V, E) が与えられたときラベルの和が最小となる全域木を作りたい全域木 G(V, T) Vのすべての頂点で構成される木最小全域木 e T Ce 9 を最小にする T で作られる G(V,T) 7 (Ceは辺 eのラベル ) 例 : ラベルを地点間の配線コストとするこのとき全地点がつながるネットワークを最小コストで配線したい 6

5 プリム法による最小全域木の作成 H a 6 7 e g b f c 6 h 7 d 考え方任意の頂点を選び開始点とする T を辺の集合とする ( 開始時は空とする ) H の領域まで最小全域木の一部を作っているとする H から出る辺のうちそのコストが最小の辺で接続する頂点を H に取り込む (*) その辺を T に追加する H=V となるまで (*) を繰り返す G(V,T) が最小全域木となる

6 プリムのアルゴリズム : 素直な実装 H := {} T := {} While H V min_length :=, min_edge := null Foreach (u,v) : u H, v H-V If min_length > length(u,v) Then, min_length := length(u,v) min_edge := (u,v) EndIf EndFor T.add ( min_edge ) H.add( min_edge.right ) EndWhile e a 6 7 g 時間計算量 O(nm) この疑似コードの場合 b f c 6 h 7 6 d

7 練習プリム法により以下のグラフに対する最小全域木を作成せよ

8 . 開始点を選ぶ 6 7 9

9 . コストが最小の辺を選び接続する頂点を取り込む (/)

10 . コストが最小の辺を選び接続する頂点を取り込む (/) 6 7 9

11 . コストが最小の辺を選び接続する頂点を取り込む (/) 6 7 9

12 . コストが最小の辺を選び接続する頂点を取り込む (/) 6 7 9

13 . コストが最小の辺を選び接続する頂点を取り込む (/) 6 7 9

14 . コストが最小の辺を選び接続する頂点を取り込む (6/) 6 7 9

15 . コストが最小の辺を選び接続する頂点を取り込む (7/) 6 7 9

16 . コストが最小の辺を選び接続する頂点を取り込む (/)

17 . コストが最小の辺を選び接続する頂点を取り込む (9/)

18 . コストが最小の辺を選び接続する頂点を取り込む (/) 6 7 9

19 . コストが最小の辺を選び接続する頂点を取り込む (/)

20 . コストが最小の辺を選び接続する頂点を取り込む (/) 6 7 9

21 . 最小全域木の完成 6 7 9

22 プリムのアルゴリズム ( 改良版 ) ダイクストラ法で工夫したようにダイクストラ法とよく似た形に実装できる H := {} T := {} While H V min_length :=, min_edge := null Foreach (u,v) : u H, v H-V If min_length > length(u,v) Then, min_length := length(u,v) min_edge := (u,v) EndIf EndFor T.add ( min_edge ) H.add( min_edge.right ) EndWhile 改良前 Foreach v V (v ) c[v] :=, prev[v]:=null Q.add(v) EndFor c[] := While Q i not empty u := Q.extractMin() Foreach v in Adj[u] If c[v] > length(u,v) Then, c[v] := length(u,v) prev[v] := u ( Q.changeKey() ) EndIf EndFor EndWhile 改良後

23 確認プリム法 ( 改良版 ) により以下のグラフに対する最小全域木を作成してみよ While Q i not empty u := Q.extractMin() Foreach v in Adj[u] If c[v] > length(u, v) Then, c[v] := length(u, v) prev[v] := u EndIf EndFor EndWhile

24 プリム法 : 計算量の考察 While 文の内部は n 回実行される Foreach 文の内部は nm 回実行される実装によっては O(nm) となりえる Q にリストや配列を使う場合 Q.extractMin() に O(n) の時間を要する Q.extractMin() は n 回呼び出される O(n ) While Q i not empty u := Q.extractMin() Foreach v in Adj[u] If c[v] > length(u, v) Then, c[v] := length(u, v) prev[v] := u ( Q.changeKey() ) EndIf EndFor EndWhile Q に分ヒープを使う場合 Q.extractMin() に O(log n) の時間を要する Q.extractMin() の呼び出しは n 回ある O(n log n) c[v] の更新に伴うヒープの組換え処理に O(log n) の時間を要する c[v] の更新は m 回発生する O(m log n) O( (n+m) log n )

25 今日の内容最小全域木プリムのアルゴリズム最大流問題フォードファルカーソンのアルゴリズム

26 最大流問題 Maximum Flow Problem ラベル付 ( 重み付 ) グラフ G(V, E) が与えられたとき流入点から流出点 t までの総流量を最大化したい辺のラベルの意味 : 流量の容量 ( 最大量 ) 運べる荷物の量流せる水の量送れるパケット数このときに流れ込む流量 = t から流れ出る流量 ( グラフの外から見た場合 ) から流れ出す流量 = t に流れ込む流量 ( グラフの中で見た場合 ) である 6 この量の最大値 ( とそのときのフロー ) をどう求めればよいか? t

27 最大流問題 : 解決へのアプローチ u v t -t 間の適当な道を考えその流量上限 ( 最小容量 ) を算出する赤色のケース赤色のフローを流しても余っている別の -t 間の道を考える ( 逆向きは押し戻すと考える ) この際の流量上限を算出する青色のケース上記を繰り返していけば徐々に総流量が増えてやがてそれ以上流せなくなるこれによりネットワーク全体の最大流が求まるのではないか?? 7

28 フローの定式化辺を流れるフロー u f(u,v) f(u, v) C(u, v) v f(v, u) = - f (u, v) -C(v, u) f(u, v) C(u, v) ただし C(u, v) = C(v, u) とは限らない C(u,v) C(v,u) 頂点への流入量と流出量 v 流入量 : f in (v) = u V, f(u,v)> f(u,v) 流出量 : f out (v) = w V, f(v,w)> f(v,w) v,t であれば f in (v) = f out (v) 総流量 : total(f)= f out () = f in (t)

29 フォードファルカーソン法 Ford-Fulkeron Algorithm 考え方 -t 間の何らかの道を考えその流量の上限 u v u v t フローに沿って - t を算出するそのフロー f を容量 C から引いた値 ( 残余容量 ) を計算しグラフから差し引くそのグラフを Gf とする Gf に対して同様のことをする ( つまり -t 間の何らかの道を考えその流量の上限を算出し総フローを算出し容量から差し引いて ) -t 間の道が無くなれば終了フローに沿って ( さらに ) - u v -t 間の道がなくなった ( 容量 > の弧についてのみ考える ) t このとき差し引いている総フローが求める最大流 9

30 練習フォードファルカーソン法を用いて以下のフローグラフにおけるから t への最大流を求めよ t (*) 辺のラベルは容量 ( 向きは問わない ) を表している

31 容量をまず有向グラフに置き換える t

32 -t 間の適当な道を考えその流量の上限を算出する t

33 残余容量 Cf(u,v) = C(u,v) - f(u,v) とし Gf を作成する t 7

34 Gf において -t 間の適当な道を考えその流量の上限を算出する t 7

35 残余容量 Cf(u,v) = C(u,v) - f(u,v) とし Gf を作成する 6 (*) 本来は f(u,v) はフローの総和道 P によって作られるフローではない t 9

36 Gf において -t 間の適当な道を考えその流量の上限を算出する 6 t 9

37 残余容量 Cf(u,v) = C(u,v) - f(u,v) とし Gf を作成する 6 7 (*) 本来は f(u,v) はフローの総和道 P によって作られるフローではない t 9

38 Gf において -t 間の適当な道を考えその流量の上限を算出する 6 ( ここでは複数回まとめて表示 ) 7 t 9

39 残余容量 Cf(u,v) = C(u,v) - f(u,v) とし Gf を作成する 6 6 (*) 本来は f(u,v) はフローの総和道 P によって作られるフローではない t 9

40 Gf において -t 間の (Cf> の辺で作られる ) 道が存在しないので終了 6 6 t 9

41 最大流は以下のフローの総和である t

42 各辺が以下のフローを通すときからtに対して最大流が得られるその流量は t t

43 フォードファルカーソンのアルゴリズム Max-Flow(G(V,E),, t) e E, f(e)= While any path from to t exit in reidual graph Gf P := imple-path(,t) in Gf f := augment(f, P) Update f to be f Update Gf to be Gf EndWhile Return f 道の発見には幅優先探索深さ優先探索などが用いられるフロー f に道 P を流れるフローの上限分を追加しそれを f に代入する処理このアルゴリズムの停止性について考察してみよ

44 今日の内容最小全域木プリムのアルゴリズム最大流問題フォードファルカーソンのアルゴリズム

45 今後の予定 6 月日 : 平面的グラフ地図 7 月日 : スキップグラフ 7 月日 : 内容未定 7 月日 : 試験 : 講義室 ( 未確定 )

離散数学

離散数学最短経路問題落合秀也その前に前回の話深さ優先探索アルゴリズム開始点から深さ優先探索を行うアルゴリズム S.pu() Wl S not mpty v := S.pop() I F[v] = l Tn, F[v] := tru For no u n A[v] S.pu(u) EnFor EnI EnWl (*) 厳密には初期化処理が必要だが省略している k 時間計算量 :O(n+m)