<4D F736F F F696E74202D D8C7689E682C68DC5934B89BB F A2E707074>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D D8C7689E682C68DC5934B89BB F A2E707074>"

せいこいたばし
5 years ago
Views:

1 分枝限定法データ構造初期値 G=,Z= A{P0},N{P0},O=φ X[0]={#,#,#,#, G, Z} 節点 0 A リスト {P0} Nリスト {P0} P0=S アクセス済み O =φ X[0]={#,#,#,#, -10, Z} P0を分枝節点 1 s # # A リスト {P0, P1, P2} N リスト {P0, P1, P2} O =φ X[0]={#,#,#,#, -10, Z} X[1]={1,0,#,#, G, Z} X[2]={1,1,#,#, G, Z}

2 分枝限定法の処理手順 (Procedure of Branch and Band) 最適解が一個の場合 A: 既に生成されているがまだ分解も終端もされていない部分問題の集合 N: 既に生成されている部分問題の集合. z: 最適値の暫定値 O: 最適解の集合. Step1 初期設定 : A={P0}, N={P0}, z=, および,O= ( 空集合 ). Step2 探索処理 : A= なら Step9 へ,A なら Pi=s(A) として Step3 へ. Step3 暫定値更新 :x S かつ f(x)<z の解 x があれば,z=f(x),O={x} とし Step4 へ. Step4 緩和問題によるテスト : 次のいづれかが成り立てば,Step8 へ, それ以外は Step5 へ (1)Pi の緩和問題 P~i が許容解を持たない. (2)g(Pi)=f(Pi), すなわち,P~i の最適値が Pi の最適値に一致する. Step5 下界値テスト :g(x) z が成立すれば,Step8 へ, それ以外は Step6 へ. Step6 優越テスト :Pi より優越する Pj が既にあれば,Step8 へ, それ以外は Step7 へ Step7 分枝処理 :Pi の子節点 Pi1,Pi2,...Pin を作り, A = A {Pi1,Pi2,...Pin}-{Pi},N = N {Pi1,Pi2,...Pin} として Step2 へ. Step8 部分問題 Pi の終端処理 : A = A-{Pi} として Step2 へ Step9 停止 z = のとき, 与えられた問題 P0 は許容解を持たない. z < のとき, 最適値 =z, 最適解は,O に記憶されている.

3 グラフとネットワークの基礎 ( 組み合わせ最適化問題の数学的バックグラウンド ) 1736 年に数学者オイラーが解法を示したのが学問の始まり. 参考書 : グラフ理論入門,R.J. ウィルソン著, 齋藤西関訳, 近代科学社グラフ頂点, 節点 (Vertex) V 辺, 枝 (Edge) E グラフ G = (V, E)

4 グラフとは? 単純グラフ多重グラフ無向グラフ定義辺 e が点対 (u,v) のとき辺 e は u と v を結ぶ (joint) 辺 e は u および v に接続する (incident) u および v は辺 e の端点 (end) と呼ばれる u=v なる辺はループ (loop) と呼ばれる同じ点対の辺は多重辺 (multiple edge) と呼ばれる辺に向きがないグラフを無向グラフ (undirected graph) 有向グラフ辺に向きがあるグラフを有向グラフ (directed graph)

5 グラフの例ループあり単連結

6 グラフの種類と応用例ネットワーク最大流量問題 ( ネットワークフロー ) ツリー ( 根付き木 ) 巡回セールスマン問題最短路問題最大流量問題 2 部グラフ分類問題

7 グラフの定義互いに素 ( = 交わらない ) な有限集合 V,E と写像 μ:e P(V) に対して, ペア G = (V, E) = (V, E; μ) をグラフ G と定義する. ここで P(V) は V のベキ集合である. V の要素 : 頂点 (vertex) もしくは点 E の要素 : 辺 (edge) V (G): G の頂点集合 E (G): G の辺集合 μ : 接合写像 V(G) = p, E(G) = q のとき (p, q) グラフ V={v1, v2, v3, v4} E={e1, e2, e3, e4, e5, e6} μ(e1)={v1, v2} μ(e2)={v1, v2} μ(e3)={v2, v3} μ(e4)={v3, v4} μ(e5)={v4, v1} e1 μ(e6)={v2, v2} V のべき集合 e6 v1 e5 e2 v2 e3 v4 e4 v3

8 グラフの用語 1( 単純グラフ ) 端点 : 辺 e の両端の点といい, 端点は e に接合している隣接 : 辺と辺がある頂点を共有しているときその辺同士ループ ( 自己ループ ): ある辺の両端点が等しいとき多重辺 :2 頂点間に複数の辺があるとき単純グラフ : ループも多重辺も含まないグラフ重み付きグラフ : 辺に重み ( コスト ) を付与したグラフ 10 μ(e1)={v1, v2} μ(e2)={v1, v2} μ(e1)={v1, v2} リンク μ(e) = 2 μ(e6)={v2, v2} ループ μ(e) = W(e1)={v1, v2, w} 出典 : フリー百科事典ウィキペディア (Wikipedia)

9 グラフの用語 2( 部分グラフ ) G は G の部分グラフ : G の頂点集合と辺集合が共に G の頂点集合と辺集合の部分集合になっているとき ( 逆 : 拡大グラフ ) 全域部分グラフ ( 生成部分グラフ因子 ): 頂点集合が等しい部分グラフ誘導部分グラフ : G の頂点集合 V の部分集合 S を取り出して両端点が S に属する全ての辺を辺集合とする G の部分グラフ縮約グラフ ( 商グラフ ): グラフ G からある辺を取り除きその辺の両端点を一つの頂点に縮約したとき部分グラフ拡大グラフ誘導部分グラフ辺の除去縮約グラフ G G

10 グラフの用語 3( 正則グラフ ) 次数 : 頂点 v に接続する枝の数 d(v) ( 入次数, 出次数 ) k- 正則 : すべての v について d(v) = k が成り立つとき正則グラフ : ある k について k- 正則なグラフ δ(g): グラフ G 中の最小次数の頂点の次数 Δ(G) 最大次数の頂点の次数孤立点 : 次数 0 の頂点 {d(v)} d(v) = 3 v V 正則グラフ

11 グラフの用語 4( 閉路 ) 歩道 ( 鎖 ): 隣接している頂点同士をたどった v 1, e 1, v 2, e 2,..., e n-1, v n の系列路 ( 小径 ): 辺の重複を許さない場合道 : 頂点の重複も許さない場合閉路 ( 回路サイクル ): 始点と終点が同じ路完全グラフ ( 完備グラフ ): 任意の 2 頂点間に枝があるグラフクリーク : 完全グラフになる誘導部分グラフサイズ n のクリークを含むグラフは n- クリークであると言う辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2- クリークであるまた n- クリークであって直径が n 未満となるグラフを n- クランと言う

12 木の性質グラフにおいて, 単連結で閉路を持たないグラフ ( 単連結とは, 辺を削除すると 2 つに分かれてしまうグラフ ) 4つの主な性質 ( 定理 ) がある 1.(T の辺の個数 )=(T の節点の個数 )-1 T = T 任意の2 点 x,y に対して x,y を結ぶただ一つの道がある 3.T の2 点を結ぶ T に含まれない辺 e に対して T+e には e を通るただ一つの閉路がありこの閉路上の任意の辺 f に対して T+e-f は木となる 4. 少なくとも2 個の端末点があるまた端末点とは次数 1の点である

13 2 部グラフ ( 分類, クラスタリング ) n 部グラフ 2 部グラフ : グラフ G のうち V(G) を二つの頂点集合に分割して各集合内の頂点同士に枝が無いように分割できるグラフ n 部グラフ : n 個の頂点集合に分割可能なグラフ完全 2 部グラフ : 二つの頂点集合 V 1, V 2 に分割したとき V 1 同士 V 2 同士の頂点間には辺が存在しないが V 1 と V 2 間の任意の 2 点間に辺が存在するグラフのことである m 頂点の頂点集合と n 頂点の頂点集合でできているとき K m, n とかく

14 直径の定義径 ( けい diameter) あるいは直径 ( ちょっけい ) とは図形の差し渡しの長さのことであるグラフ理論でいう直径とはグラフ上の任意の 2 頂点間の距離の最大値一般に任意の距離空間の部分集合 ( つまり図形 ) に対してその集合に含まれる二点の距離の上限として直径を考えることができる ( 上限が存在しないときには直径は無限大とする ) つまり d(x, y) で二点 x, y の距離を表すとき集合 S の直径 diam S はで与えられる直径が有限な値を持つときその集合は有界であるといわれるユークリッド空間の部分集合の場合有界の定義は原点を中心とする十分大きな球にその集合が含まれることであるとしても同じことになる

15 同型グラフ G と G' が同一の頂点を持ち同一の辺のつながりかたをしているとき同型という 2 つのグラフ G と H が等しい G = H とは V(G) = V(H),E(G) = E(H),μ G = μ H のときで同型 G ~ H の定義全単射 θ:v(g) V(H),χ:E(G) E(H) が存在して,μ G (e) = {u, v} μ H (χ(e)) = {θ(u), θ(v)} となるとき,

16 連結グラフ連結グラフ : グラフ上の任意の2 頂点間に路が存在するグラフ ( 極大で連結な部分グラフは連結成分 ) 有向グラフが強連結であるとはグラフ上の任意の2 点間に有向路が存在すること ( 極大で強連結な部分グラフは強連結成分 ) 切断点または関節点 : 連結なグラフGからある頂点を取り除くと G が非連結になるときその頂点切断辺または橋 :Gからある辺を取り除くと Gが非連結になるときその辺グラフがどの程度かたく結びついているかを示す尺度として点連結度 ( あるいは単に連結度 ) と辺連結度がある k 連結グラフは点連結度がk 以上のグラフのことを指す連結グラフ非連結グラフ

17 平面グラフ平面グラフ (plane graph) : 平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフ

18 12 月 24 日グラフ理論グラフの基本的性質グラフの探索ダイクストラ法

19 グラフの基本的な性質 ( 復習 ) グラフの全ての点の次数を合計すると偶数になる ( 握手問題, オイラー ) 奇数次の点は偶数個ある N 部グラフ, 木構造には三角形は存在しない

20 例題 : パズル問題グラフ理論を用いた問題解決 ( 急性精神病 ) 4 個の立方体の積み木問題立方体は 4 色に塗り分けられている. これらの立方体を積み上げて四角柱を作る四角柱の側面それぞれに 4 色全部が現れるような積み方を求める問題 ➂ ➀ ➃ ➁

21 表裏の色の関係をグラフ化する ➀ ➁ ➂ ➃

22 グラフを重ね合わせる前後部分グラフをとると前後左右それぞれすべての色を持つことができる左右

23 演習問題北海道大学複雑系工学講座 ( 井上純一先生作成 ) 1. グラフ G(V, E) について次の問に答えよただし,V = {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E}, {B,F}, {C,F}, {D,E}} である (1) 頂点 A と C の距離 d(a, C) はいくらか (2) このグラフの直径を求めよ (3) このグラフに切断点はあるかもしあればすべての切断点を列挙せよなければなしと答えよ

24 A D E 解答 B F C 1. グラフ G(V, E) について次の問に答えよただし,V = {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E}, {B,F}, {C,F}, {D,E}} である (1) 頂点 A と C の距離 d(a, C) はいくらか解答 d(a, C) は, 頂点 A から C への最短の道の長さであるそのような最短道は, 頂点の列 (A, B, F, C) で表され, この道には 3 つの辺が含まれているので,d(A, C) = 3 である (2) このグラフの直径を求めよ解答直径は, このグラフ上の任意の 2 頂点間の距離の最大値である最も距離が大きくなる 2 頂点の片方は頂点 C となることは分かる頂点 C から他の頂点への距離を調べると,d(C, D) = 4 が最大となるよって, このグラフの直径は 4 である (3) このグラフに切断点はあるかもしあればすべての切断点を列挙せよなければなしと答えよ解答切断点は B と F の 2 つ C は切断点ではないことに注意せよ

25 オイラー路 ( 数学者レオンハルトオイラー ( スイスバーゼル )) オイラー路 : グラフの全ての辺を 1 度だけ通る路オイラー閉路 : 全ての辺を 1 度だけ通る閉路オイラーグラフ : オイラー閉路を含むグラフ準オイラーグラフ : オイラー閉路は持たないがオイラー路を持つグラフ性質オイラーグラフと準オイラーグラフは一筆書き可能であるオイラーグラフ全ての頂点の次数が偶数のグラフ準オイラーグラフ奇数の次数の頂点を二つだけ含むグラフ参考 : オイラーの等式, オイラーマクローリン展開, 変分法, 一巡閉路オイラーグラフ準オイラーグラフ

26 オイラー路の判定法条件 1) 有限グラフ ( 辺の数も頂点の数も ) で連結 (connected) なグラフに限定. において, 1) 始点終点以外の全ての頂点において, 入ってくる辺の数と出て行く辺の数が同じはずなので, その頂点の次数は偶数 2) 始点と終点は次数が奇数である ( 出発のときの出るだけの辺が一つ半端だから. 終点についても同様 ) オイラー路の存在条件 : 1),2) オイラー閉路の存在条件 : 全ての頂点が偶数の次数をもつこと.

27 オイラー路 ( 例題 ) 例題 V={A,B,C,D,E,F,G}, E={s,t,u,v,w,x,y,r}, T(s)={A,E}, T(t)={E,B}, T(u)={B,C}, T(v)={C,F}, T(w)={F,D}, T(x)={A,D}, T(y)={E,F}, T(z)={E,G}, T(r)={G,F}, のときオイラー回路は存在するか答え : E,F の次数は 4, 他は 2 全て偶数なのでオイラー回路が存在する. アルゴリズム 1 ( 枚挙法 ) Step1 始点を選ぶ Step2 S から t までを並べ替える (M! 通り ) Step3 閉路になるかどうか調べるアルゴリズム 2 ( グラフ理論の応用 ) Step1 点の次数が偶数か奇数か? Step2 調べていない点があれば S1 へ (M 通り )

28 ハミルトン路 ( ウィリアムローワンハミルトン ( 英国 )) ハミルトン路 : グラフ上の全ての頂点を 1 度だけずつ通る路ハミルトン閉路 : グラフ上の全ての頂点を 1 度だけずつ通る閉路ハミルトングラフ : ハミルトン閉路を含むグラフ準ハミルトングラフ : ハミルトングラフではないがハミルトン路を含むグラフ与えられたグラフがハミルトン路を含むかどうか判定する問題は NP 困難

29 ハミルトングラフの性質 1 1. V(G) 3 δ(g) V(G) /2 を満たす単純グラフ G はハミルトングラフ (Dirac, 1952 年 ) 頂点の数 V(G) 最低次数 δ(g) 単純グラフ G

30 ハミルトングラフの性質 2 1. グラフ G ( V(G) 3) がハミルトングラフ d(u) + d(v) V(G) を満たす隣接していない頂点 u, v について G + (u, v) がハミルトングラフ 2. グラフ G ( V(G) 3) がハミルトングラフで (u, v) E(G) かつ d(u) + d(v) n + 2 ならば G - e もハミルトングラフ d(u) + d(v) (u, v) G

31 ハミルトングラフの性質 3 1. 完全グラフ K 2n+1 は n 個のハミルトン閉路に分解できる 2. 完全グラフ K 2n は n-1 個のハミルトン閉路と 1 個の 1- 正則な全域部分グラフに分解できる 1- 正則な全域部分グラフ K 5 K 6

32 演習問題 ( つづき 1) グラフ V = {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E}, {B,F}, {C,F}, {D,E}} (4) このグラフはオイラーグラフか? また, ハミルトングラフか? (5) このグラフは 2 部グラフか? (6) このグラフから何本かの辺を除去して木にするには, 何本を除去すればよいか

33 解答 D A E B F グラフ V = {A, B, C, D, E, F}, E = {{A,B}, {A,D}, {B,E}, {B,F}, {C,F}, {D,E}} C (4) このグラフはオイラーグラフか? また, ハミルトングラフか? 次数が奇数である頂点 ( 奇頂点という ) が B と C の 2 個あるので, オイラーグラフではない ( 周回可能小道はあるが, 閉じていないのでオイラー小道ではない ) また, 頂点 C は次数が 1 であるので C を通るような閉路 ( 閉じた道なので, その通り道の次数は 2 以上でないといけない ) は存在しない従って, ハミルトン閉路は存在しないつまりハミルトングラフでもない [ 頂点 C を通る閉路がないのだから, もちろんオイラー小道がないということもできる ] (5) このグラフは 2 部グラフか? 解答 2 部グラフである頂点 A,E および F を左側に書き, 残りの頂点を右側に書けば, すべての辺は左側の頂点と右側の頂点を結ぶことになる (6) このグラフから何本かの辺を除去して木にするには, 何本を除去すればよいか解答 1 本を除去すれば木になるただし, 辺 {A,B},{B,C},{C,D} または {D,A} のいずれかを除去すると木になるが, これ以外の辺を除去しても木にはならないつまり, このグラフに閉路がなくなるように辺を除去しなくてはならない

34 隣接行列隣接行列 : 隣接関係を表す行列 n 頂点のグラフ G に対して, A(G) = a 11 a 12 a 1n a 21 a 22 a 2n... a n1 a n2 a nn 頂点 vi から頂点 vj への辺がある a ij = 1 頂点 vi から頂点 vj への辺がない a ij = 0 無向グラフ a ij = a ji 行の和 = 次数

35 根つき木の探索法節点 vから枝分かれする点の集合 T(v) 0) A = {v 0, v 1, v 2 v n }, B = {v 0 } 1) Aから一つの成分 vを取り出し,t(v) の中でBに入っていないものをAとBに入れる. 2) Aが空なら終了そうでなければ1) へ v 0 先にいれたものを先に取り出すキュー (queue) 後にいれたものを先に取り出すスタック (stack) 幅優先探索キュー深さ優先探索スタック評価値優先

36 最短路問題長さつきネットワーク G=(E,V,W) s 例自宅の最寄り駅から四ッ谷駅までの鉄道の最短時間 ( もしくは最安 ) ルートを求める ( 駅ナビなど ) カーナビを使って現在地から目的地までの最短経路を調べる s t への最短路一般的な解法動的計画法 DP 分枝限定法ダイクストラ法

37 ダイクストラ法 (Dijkstra Method) 最短経路問題は, やさしい部類の問題であり, 全経路を調べることなく効率的に最短経路が求められるアルゴリズムが存在する. ダイクストラ法の特徴出発点を 1 つに固定してそこから他のすべての頂点への最短路を求める方法出発点に近い頂点への最短経路を次々に求める方法

38 ダイクストラ法の手順 1. 出発点に隣接する頂点の出発点 - 頂点間の距離を求め最小の値をもつ頂点にマークを付けて確定する 2. マークのついた頂点に隣接する頂点までの距離を求めこの時点で計算されている頂点 ( マークの付いていない ) の距離の中で最小の値をもつ頂点をマークして確定する 3. 以上の操作をすべての頂点にマークがつくまで繰り返すと各頂点に得られる値が出発点からの最短路となる s V={1, 2, 3, 4, 5} : 頂点集合 N={, 50,, 80, : 隣接行列,, 15, 20,,,, 30, 15,,,, 50,,,, } 5

39 ダイクストラ法のアルゴリズム i から j への長さ aij 0 d(i):s から i への最短長さの上限 p(i):i への最短路へのポインタ T(v):v から出る節点の集合手続き (Procedure) 0) d(s) = 0, d(i) = (i s) A = φ, A= V 1) A = V ならば終了そうでなければ { } dv () = min di () i A 2) A = A {} v A = A {} v Tv () A d(j) > d(v) + a vj ならば d(j) = d(v) + a vj p(j) = v 1) への節点 j に対し

40 演習問題 ( つづき 2) 2. グラフ G が与えられているとする G の補グラフ G は,G と同じ頂点集合をもち,G において 2 頂点 u と v の間に辺が存在しないとき, かつそのときに限り,G において u と v の間に辺が存在するようにしてできるグラフである次の問に答えよ (1) グラフ G(V, E) の補グラフ G を書けただし,V = {A, B, C, D, E}, E = {{A,C}, {B,D}, {B,E}, {C,D}, {D,E}} である ( このグラフを図に描いてから考えてください ) (2) 上のグラフ G の隣接行列 A およびその補グラフ G' の隣接行列 A' を完成せよ (3) 頂点数 4 のグラフ G で,G と G が同形であるようなグラフを書け (4) 頂点数 8 のグラフ G で,G と G' が同形であるとすれば, このグラフ G には辺が何本あるか

41 解答 2. グラフ G が与えられているとする G の補グラフ G は,G と同じ頂点集合をもち,G において 2 頂点 u と v の間に辺が存在しないとき, かつそのときに限り,G において u と v の間に辺が存在するようにしてできるグラフである次の問に答えよ (1) グラフ G(V, E) の補グラフ G を書けただし,V = {A, B, C, D, E}, E = {{A,C}, {B,D}, {B,E}, {C,D}, {D,E}} である ( このグラフを図に描いてから考えてください ) 解答補グラフ G の辺集合 E は E = {{A,B}, {A,D}, {A,E}, {B,C}, {C,E}} となる (2) 上のグラフ G の隣接行列 A およびその補グラフ G' の隣接行列 A' を完成せよ解答... 行列は, いつものように書く A = [ ] A' = [ ] (3) 頂点数 4 のグラフ G で,G と G が同形であるようなグラフを書け解答長さ 3 の道 ( 図 5-26 の (d) のグラフ ) 練習問題 : 頂点数 5 のグラフ G で,G と G が同形であるようなグラフは 2 種類ある考えてみよまた, 頂点数 6 や 7 の場合はどうかも考えよ (4) 頂点数 8 のグラフ G で,G と G' が同形であるとすれば, このグラフ G には辺が何本あるか解答辺が n 本あるとすると,G' にも n 本あるこれらの和 2n は頂点数 8 の完全グラフの辺の本数 8 (8-1)/2 = 28 に等しいすなわち,2n = 28 であるから,n = 14 である

42 ファイル名の書式学生番号名前課題番号.Doc ( 数字 ) ( 漢字 ) ( 数字 ) 課題番号については, 1. ランダム探索 (TSP) 2. 分枝限定法 ( ナップザック ) 3. 分枝限定法 (TSP) 4. ダイクストラ法 ( 最短経路 ) ボーナス点

43 レポートの書き方表紙 : 学生番号名前課題番号, 日時課題内容方法論実現方法 ( プログラム解説 ) 解析結果考察感想

オートマトンと言語

オートマトンと言語 4 回目 5 月 2 日 ( 水 ) 3 章 ( グラフ ) の続き授業資料 http://ir.cs.yamanashi.ac.jp/~ysuzuki/public/automaton/ 授業の予定 ( 中間試験まで ) 回数月日内容 4 月日オートマトンとは, オリエンテーション 2 4 月 8 日 2 章 ( 数式の記法, スタック,BNF) 3 4 月 25 日 2