アルゴリズム論第 (1クラス) 第 14 回 (2018/01/17) 情報学専攻庄野逸 (shouno@uc.c.jp) ( 3 号館 313 号室 )
本 のお題 [ 復習 ] グラフとは グラフの基本概念と 語 グラフの実現 法 グラフを いた問題 最短経路問題 Dijkstr アルゴリズム,APSP 問題と Floy アルゴリズム 有向グラフ (DAG) とトポロジカルソート 最 全域 (Minimum Spning Tr): Prim と Kruskl のアルゴリズム グラフの 2 重連結性 グラフのマッチング ( の紹介 )
[ 復習 ] グラフとは? 語説明 (1) 雑把にいえば 幾つかの点とそれらを結ぶ線からなる図 がグラフ 点は, 頂点 (Vrtx)/ 節点 (No) などと呼ぶ 頂点集合を V とする.2 頂点 v, w V を結ぶ線 = (v, w) V x V を辺 (g) / 枝 (rnch) と呼ぶ v と w は の端点 (n nos) V: 頂点集合,E: 辺集合とした時, グラフはこれら 2 つの集合できるグラフ G = (V, E) 無向グラフ (Unirct Grph) 辺は頂点を結ぶだけで向き (irction) がない.(v,w) = (w, v) 有向グラフ (Dirct Grph) 辺に向きがある v w (w は v に隣接する ) この場合の辺を 弧 (rc) と呼ぶ.
[ 復習 ] グラフとは? 語説明 (2) 雑把にいえば 幾つかの点とそれらを結ぶ線からなる図 がグラフ 経路 : 頂点の列 v 1, v 2,... v n. ただし (v i, v i+1 ) E ( 辺が存在する ) 経路の さ : 通過する辺の本数 = 両端も含めた点の個数 -1 つの頂点だけの経路は, さ 0 単純経路 (simpl) 最初と最後以外の全ての頂点が異なる 閉路 (cycl, circuit) ある頂点から, その頂点 へと る単純な経路有向グラフでは さが 1 以上. 無向グラフでは さが 3 以上 : つのノードを根とし, どのノードについても, 根からの単純な経路が つだけあるグラフ
問題のモデル化とグラフ 最短経路問題 A 地点から B 地点へ くのにいろいろな経路がある時, 番 ( 安い, 早い, 楽な ) 経路は? トポロジカルソート さな作業 程の組合せ ( 順序関係あり ) からなる仕事を仕上げる場合, 全ての 程をどのような順番で作業を進めるか? コスト最 の極 幾つかの町に通信線を引くのに, どの町にも連絡がつき, かつ最もコストかからない 法は? グラフの 2 重連結性幾つかの町のネットワークがあったとして, 部が機能しなくなっても全体の連結性が失われないようなネットワークを作るには? グラフマッチング によってこなせる仕事が異なる場合, どの仕事をどの に割り振るか
[ 復習 ] グラフの表現 実現 法 (1) ラベル付き隣接 列 (jcncy mtrix) 隣接の集合が V = {v 1,..., v n } の時, 要素が論理型の n x n 列 A において (v i, v j ) E ならば A ij は真, そうでなければ偽とする 無向グラフならば 列は対称 列になる グラフがラベル付きの場合,A の要素を辺のラベルにすると良い c c
[ 復習 ] グラフの表現 実現 法 (2) 隣接リスト (jcncy list) 各頂点において隣接する頂点のリストを保持 リストは連結リストやカーソルによって実現 c c
[ 復習 ] 最短経路問題と ダイクストラアルゴリズム (1) 50 2 10 0 3 10 20 1 30 4 100 5 (Dijkstr) : V = {1, 2,...,n} E (i, j) E C(i, j) ( (i, j) C(i, j) = ) : 1 j(= 2,...,n) (j)... (1) S := {1}; or j := 2 to n o (j) :=C(1,j); (2) n 1 (S = V ) (2-) S (u) u (2-) S := S { u }; (2-c) u (u, v) E (v) min( (v), (u) +C(u, v)); (v u )
[ 復習 ] 最短経路問題と ダイクストラアルゴリズム (2) 1 から到達するためのコスト 1. 経由地 2, (u=2) = 10 S = {1, 2}, 更新 v= 3 2. 経由地 4, (u=4) = 30 S = {1, 2, 4}, 更新 v = 3, 5 3. 経由地 3, (u=3) = 50 s = {1, 2, 3, 4}, v = 5 4. 残った 5 を始点とする弧がないので終了
最短経路問題の解法と計算量 隣接 列による表現 n 個の要素の集合 S をビットベクトルで表し,(j) および C(i, j) を, そのまま各々 1 次元および 2 次元の配列で表すのが 番簡単 ステップ (2-) およびベクトル要素の操作の計算量は, それぞれ O(n) 全体で O(n 2 ) 計算量を良くするための実現法 隣接リスト表現. 各点からの辺を連結リストで保持 (u) を優先度とするヒープを考える. 但しヒープノードには, 優先度とグラフの頂点番号 u の組を保持ヒープの要素数は n ステップ (2-) における要素の選択 (DltMin) の 間, ステップ (2-c) で (v) の値が変更された場合のヒープ内の位置変更 (insrt) も 間は O(log n). ステップ (2-) は n 回, (2-c) は E ( 辺の数 ) 般には E > n なので, 全体の計算量は O( E log n)
最短経路問題 : 全ての頂点つの 最短経路 (1) APSP 問題出発点を つに限定せずに, グラフ上の任意の 2 頂点について最短経路を求める問題を APSP(All Pirs Shortst Pths) 問題と呼ぶ ダイクストラアルゴリズムを全頂点を始点にして実 する 隣接 列を使うのならば フロイド (Floy) アルゴリズム も n x n 隣接 列 A を考える. 対 要素 A ii = 0, それ以外は A ij = C(i,j) k = 1 n i = 1 n j = 1 n で 3 重ループを回す A ij = min( A ij, A ik + A kj ) k 回操作後の A ij は 頂点 i から j への経路のうち k より きい番号の頂点を通過しないものの最短距離 上の代 で値が変更されるのは, 頂点 i から j への経路 が k を通過することにより短くなる場合. 経路も求めたければ i-j 間の途中経路を記録する n x n 列 P も 意し, 上の代 で値が変化する場合 P[i, j] = k とすれば良い
最短経路問題 : 全ての頂点つの 最短経路 (2) APSP 問題出発点を つに限定せずに, グラフ上の任意の 2 頂点について最短経路を求める問題を APSP(All Pirs Shortst Pths) 問題と呼ぶ フロイドのアルゴリズム
最短経路問題 : 全ての頂点つの 最短経路 (3) i から j までの経路があるか? だけを知るには, 要素が真偽値のみの隣接 列の 推移的閉包 を計算する (Wrshll アルゴリズム ) 有向グラフの 中 : 離 率が最 の頂点 ( 最も遠い頂点までの距離が最も さい頂点 ) ある頂点の 離 率 = mx { w から v への最短距離 } フロイドアルゴリズムの実 終了後に得られた A を いると良い v の離 率 = mx { A uv } ( 第 v 列中の最 値 ) 練習問題有向グラフの頂点が V = {,,c,, } で 7 本だけある弧のコストが C(,) = C(, ) = 1, C(, c) = C(c, ) = 2, C(, c) = 3, C(c, ) =4, C(, ) =5 としたとき,APSP 問題をとき, 各頂点の離 率とグラフの中 を求めなさい
幅優先探索 (Brth First Srch) と 深さ優先探索 (Dpth First Srch) BFS アルゴリズム (G, s) 概略 グラフ G の s 以外の全ノードの未達とする Enq(Q, s) s c whil Q!= 空集合 v = Dq(Q) g h or u v の隣接ノード u の到達距離 = v の到達距離 +1 Enq(Q, u) v に到達済みのマークを れる Dijkstr アルゴリズムと似ている
幅優先探索 (Brth First Srch) と 深さ優先探索 (Dpth First Srch) DFS アルゴリズム (G, s) 概略 ( 再帰版 ) s に処理開始マークを れる or u s の隣接ノードかつ未処理開始 s DFS アルゴリズム (G, u) s に処理終了マークを れる g h (3/) (2/9) (1/10) (11/1) s g h 複数の 構造 森 を構成する弧 辺 先祖に戻る弧 後退弧 を跨ぐ弧 交差弧 孫以降への弧 前進弧 (7/8) (4/5) (12/13) (14/15)
閉路の無い有向グラフ (Dirct Acyclic Grph)DAG 算術式の共通部分式 ((+) * c) * (((+)*c) + ((+)+)*(+)) 式の値を計算する場合, 共通部分式の計算を 度やって覚えておけば, 同じ計算を繰り返さずに済む 閉路があるかどうか = 深さ優先探索で後退弧に出会うか? グラフをなぞる頂点間に順序を設け, 頂点毎に訪問済みか否かのマークをいれる 深さ優先の極 森 (Spnning Tr): 深さ優先探索の の弧全体 深さ優先探索の極 森の中で先祖の頂点に向かう弧を後退弧と呼ぶ 交差弧は先祖でも 孫でも無い頂点に向かう弧
DFS と極 森
トポロジカルソート トポロジカルソート : グラフの 列化.DAG の頂点に線形順序を与え, 頂点 i から頂点 j への弧があれば, その線形順序の中で i < j とする作業 DFS で終了時刻の降順に並べると,DAG の場合, 印が左から右へ並ぶので トポロジカルソート と呼ぶ 左図の DAG のトポロジカルソートを考えて なさい
無向グラフの応 : Minimumcost Spnning Tr 最 全域 (Miniml cost Spnning Tr) 幾つかの節点と 2 節点を結ぶ為のコストが与えられた時, 最 コストで全ての節点を結ぶ連結グラフ グラフ G の全域 : G の全ての頂点を連結する 由 経路 v 1... v n は v 1 と v n を 連結 する 連結グラフ (connct grph): 全ての頂点の対が連結されている 由 : 閉路の無い連結グラフ 全域 のコスト = 辺のコストの和
MST を求めるアルゴリズム Prim のアルゴリズム現在の と, その に含まれない頂点を結ぶ辺で, 重みが最 のものを に加えて育てていく O( V 2 ) Kruskl のアルゴリズム の集合で,2 つの を結ぶ辺の内で, 重み最 のものを加えることで つの に繋いでいく
MST を求めるアルゴリズム Prim のアルゴリズム (1) Prim のアルゴリズム (Prim) : V = {v i, 1 i n} (v i,v j ) C(v i,v j )( (v i,v j ) C(v i,v j )= ) : T... (1) T := ; ( ) U := {v 1 }; V U w ( V U) U (u, w) C min (w) min (w) = u U : C min (w) :=C(v 1,w), min (w) :=v 1 or w = v 2,...,v n V U. (2) U = V ( n 1 )... O(n 2 ) () U V U U V U (u, v), u U, v V U ( C min (v))...o(n) () U := U {v}; T := T { (u, v)}; C min (v) := ; (c) V U w ( V U) C(v, w) <C min (w) C min (w) :=C(v, w) min (w) :=v;... O(n)
Prim のアルゴリズム MST を求めるアルゴリズム Prim のアルゴリズム (2)? : U 1 5 (5) (5) c () (3) () (4) (2) = 1 5 5 c (3) () 4 (2) = 1 5 c (3) 4 2 = 1 5 c (3) 4 2 = 1 5 c 3 4 2 = 1 5 5 5 c 3 : C min () min () 1 O(n 2 ) 4 2
MST を求めるアルゴリズム Kruskl のアルゴリズム (1) Kruskl のアルゴリズム (Kruskl) : V E : T... (1) T := ; ( ) S := E ( ) ; C V ( ) : C := {{v } v V }) (2) C 2 C 2 () S (v 1,v 2 ) () C v 1 v 2 c(v 1 ) c(v 2 ) (c) c(v 1 ) c(v 2 ) C c(v 1 ) c(v 2 ) C (C := C { c(v 1 ),c(v 2 ) } { c(v 1 ) c(v 2 ) };) T (v 1,v 2 ) (T := T { (u, v)};)
MST を求めるアルゴリズム Kruskl のアルゴリズム (2) Kruskl のアルゴリズム? 1 5 5 5 c 3 4 2 = 1 5 5 5 c 3 4 2 = 1 5 5 5 3 c 4 2 = 1 5 5 5 3 c 4 2 = 1 5 5 5 3 c 4 2
MST を求めるアルゴリズム Kruskl のアルゴリズム (3) Kruskl のアルゴリズムにおけるデータ表現法 辺の集合 S は重みの さい順から要素を取り出していく 初期化時に重みの さい順にソートして配列やリストとしても良いし, 全ての要素を使うわけでもないので, 辺の重みで優先順位を付けたヒープを いてもよい O( E log E ) 頂点の集合を要素とする集合 C: V 中の頂点を幾つかに分けて出来た部分集合の集合 (2)-() はある頂点 v がどの部分集合に属するかの in 操作 (2)-(c) は 2 つの部分集合の併合 (mrg) 操作 データ構造 : 部分集合は 構造 が親を指す 構造があると良い ( 配列で実現可能, 親の添字を持つ ) 部分集合は要素数を保持し, 根で区別. の さは 々 O(log n) c 0 1 2 3 4 5 c 0 1 0 0 1 3 4 2
グラフの 2 重連結性 問い : 2 つの頂点間に複数の経路が存在するか? 関節点 (rticultion point): 消去するとグラフが 連結になる節点. 連結になる辺は橋 (rig) と呼ぶ 関節点を持たないグラフを 2 重連結グラフと呼ぶ 関節点を探すには? グラフ G の深さ優先探索 を構築し, 掛け順になぞる 各頂点について, の弧を 孫へと向かうか後退辺により連結する頂点の番号で最 の頂点を再帰的に求める 深さ優先 の根は, 弧が 2 以上あれば関節点. 根でない頂点は到達可能名頂点の番号が頂点の番号以上でれば関節点 ( ) c g
グラフのマッチング 2 部グラフ (iprtit grph): 頂点が互いに素な ( 共通部分のない )2 つの集合に分割され, 辺は 2 つの部分集合間を結ぶものに限られるグラフ グラフ G(V, E) が与えられた時, 辺の集合 E の部分集合で, どの 2 本の辺も V の同じ頂点に接続していないもの をマッチングと呼ぶ ( 頂点の対応づけで頂点に重複の無いもの ) 最 マッチング マッチングにおいて, 最も多くの辺を もの 完全マッチング 全ての頂点がいずれかの辺の端点になっている完全マッチングは最 マッチング を表す頂点の集合と, 同時に処理しないといけない仕事を表す頂点集合があって, 担当可能な対応関係を辺とするとそれは 2 部グラフとなる. 最 効率で仕事をしようとすると最 マッチングを解く必要が出て来る
最 マッチングを求める (Hopcrot-Krp の概要 ) マッチング M に対し M に関する増加路 : M 中のどの辺の端点にもなっていない 2 つの頂点を連結する経路のうち辺が 本おきに M に含まれるもの M と M に関する増加路の辺の集合 P との排他的論理和 M P をもとめ, それを新たな M とする という操作を増加路が つからなくなるまで繰り返す 1. 2 M ( (1,), (2,), (3,), (4,c)) 1 2 3 4 5 c 2. 5? 5-1 -3 5-1 c-4-2 or 5-1 c-4 ( ) 1 2 3 4 5 c 3. ( ) 1 2 3 4 5 c