分枝限定法データ構造 初期値 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}
分枝限定法の処理手順 (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 に記憶されている.
グラフとネットワークの基礎 ( 組み合わせ最適化問題の数学的バックグラウンド ) 1736 年に数学者オイラーが解法を示したのが学問の始まり. 参考書 : グラフ理論入門,R.J. ウィルソン著, 齋藤 西関訳, 近代科学社 グラフ 頂点, 節点 (Vertex) V 辺, 枝 (Edge) E グラフ G = (V, E)
グラフとは? 単純グラフ 多重グラフ 無向グラフ 定義 辺 e が点対 (u,v) のとき 辺 e は u と v を結ぶ (joint) 辺 e は u および v に接続する (incident) u および v は辺 e の端点 (end) と呼ばれる u=v なる辺はループ (loop) と呼ばれる 同じ点対の辺は多重辺 (multiple edge) と呼ばれる 辺に向きがないグラフを無向グラフ (undirected graph) 有向グラフ 辺に向きがあるグラフを有向グラフ (directed graph)
グラフの例 ループあり 単連結 http://coolee.at.infoseek.co.jp/graphtheory.html#1
グラフの種類と応用例 ネットワーク 最大流量問題 ( ネットワークフロー ) ツリー ( 根付き木 ) 巡回セールスマン問題 最短路問題 最大流量問題 2 部グラフ 分類問題
グラフの定義 互いに素 ( = 交わらない ) な有限集合 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
グラフの用語 1( 単純グラフ ) 端点 : 辺 e の両端の点といい, 端点は e に接合している 隣接 : 辺と辺がある頂点を共有しているとき その辺同士 ループ ( 自己ループ ): ある辺の両端点が等しいとき 多重辺 :2 頂点間に複数の辺があるとき 単純グラフ : ループも多重辺も含まないグラフ 重み付きグラフ : 辺に重み ( コスト ) を付与したグラフ 10 μ(e1)={v1, v2} μ(e2)={v1, v2} μ(e1)={v1, v2} リンク μ(e) = 2 μ(e6)={v2, v2} ループ μ(e) = 1 5 5 20 W(e1)={v1, v2, w} 出典 : フリー百科事典 ウィキペディア (Wikipedia)
グラフの用語 2( 部分グラフ ) G は G の部分グラフ : G の頂点集合と辺集合が共に G の頂点集合と辺集合の部分集合になっているとき ( 逆 : 拡大グラフ ) 全域部分グラフ ( 生成部分グラフ 因子 ): 頂点集合が等しい部分グラフ 誘導部分グラフ : G の頂点集合 V の部分集合 S を取り出して 両端点が S に属する全ての辺を辺集合とする G の部分グラフ 縮約グラフ ( 商グラフ ): グラフ G からある辺を取り除き その辺の両端点を一つの頂点に縮約したとき 部分グラフ 拡大グラフ 誘導部分グラフ 辺の除去縮約グラフ G G
グラフの用語 3( 正則グラフ ) 次数 : 頂点 v に接続する枝の数 d(v) ( 入次数, 出次数 ) k- 正則 : すべての v について d(v) = k が成り立つとき 正則グラフ : ある k について k- 正則なグラフ δ(g): グラフ G 中の最小次数の頂点の次数 Δ(G) 最大次数の頂点の次数 孤立点 : 次数 0 の頂点 {d(v)} d(v) = 3 v V 正則グラフ
グラフの用語 4( 閉路 ) 歩道 ( 鎖 ): 隣接している頂点同士をたどった v 1, e 1, v 2, e 2,..., e n-1, v n の系列 路 ( 小径 ): 辺の重複を許さない場合 道 : 頂点の重複も許さない場合 閉路 ( 回路 サイクル ): 始点と終点が同じ路 完全グラフ ( 完備グラフ ): 任意の 2 頂点間に枝があるグラフ クリーク : 完全グラフになる誘導部分グラフ サイズ n のクリークを含むグラフは n- クリークである と言う 辺を持つグラフは必ず 2 頂点の完全グラフを含むので 2- クリークである また n- クリークであって 直径が n 未満となるグラフを n- クランと言う
木の性質 グラフにおいて, 単連結で閉路を持たないグラフ ( 単連結とは, 辺を削除すると 2 つに分かれてしまうグラフ ) 4つの主な性質 ( 定理 ) がある 1.(T の辺の個数 )=(T の節点の個数 )-1 T = T - 1 2. 任意の2 点 x,y に対して x,y を結ぶただ一つの道がある 3.T の2 点を結ぶ T に含まれない辺 e に対して T+e には e を通るただ一つの閉路があり この閉路上の任意の辺 f に対して T+e-f は木となる 4. 少なくとも2 個の端末点がある また 端末点とは次数 1の点である
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 とかく
直径の定義 径 ( けい diameter) あるいは直径 ( ちょっけい ) とは 図形の差し渡しの長さのことである グラフ理論でいう直径とは グラフ上の任意の 2 頂点間の距離の最大値 一般に 任意の距離空間の部分集合 ( つまり図形 ) に対して その集合に含まれる二点の距離の上限として直径を考えることができる ( 上限が存在しないときには直径は無限大とする ) つまり d(x, y) で二点 x, y の距離を表すとき 集合 S の直径 diam S は で与えられる 直径が有限な値を持つとき その集合は有界であるといわれる ユークリッド空間の部分集合の場合 有界の定義は原点を中心とする十分大きな球にその集合が含まれることであるとしても同じことになる
同型グラフ 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)} となるとき,
連結グラフ 連結グラフ : グラフ上の任意の2 頂点間に路が存在するグラフ ( 極大で連結な部分グラフは 連結成分 ) 有向グラフが強連結であるとは グラフ上の任意の2 点間に有向路が存在すること ( 極大で強連結な部分グラフは 強連結成分 ) 切断点または関節点 : 連結なグラフGから ある頂点を取り除くと G が非連結になるとき その頂点 切断辺または橋 :Gから ある辺を取り除くと Gが非連結になるとき その辺 グラフがどの程度 かたく結びついているかを示す尺度として 点連結度 ( あるいは単に連結度 ) と辺連結度がある k 連結グラフは 点連結度がk 以上のグラフのことを指す 連結グラフ 非連結グラフ
平面グラフ 平面グラフ (plane graph) : 平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフ
12 月 24 日 グラフ理論 グラフの基本的性質 グラフの探索 ダイクストラ法
グラフの基本的な性質 ( 復習 ) グラフの全ての点の次数を合計すると偶数になる ( 握手問題, オイラー ) 奇数次の点は偶数個ある N 部グラフ, 木構造には三角形は存在しない
例題 : パズル問題グラフ理論を用いた問題解決 ( 急性精神病 ) 4 個の立方体の積み木問題 立方体は 4 色に塗り分けられている. これらの立方体を積み上げて四角柱を作る 四角柱の側面それぞれに 4 色全部が現れるような積み方を求める問題 ➂ ➀ ➃ ➁
表裏の色の関係をグラフ化する ➀ ➁ ➂ ➃
グラフを重ね合わせる 前後 部分グラフをとると 前後 左右それぞれすべての色を持つことができる 左右
演習問題 北海道大学複雑系工学講座 ( 井上純一先生作成 ) 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) このグラフに切断点はあるか もしあればすべての切断点を列挙せよ なければ なし と答えよ
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 は切断点ではないことに注意せよ
オイラー路 ( 数学者レオンハルト オイラー ( スイス バーゼル )) オイラー路 : グラフの全ての辺を 1 度だけ通る路 オイラー閉路 : 全ての辺を 1 度だけ通る閉路 オイラーグラフ : オイラー閉路を含むグラフ 準オイラーグラフ : オイラー閉路は持たないがオイラー路を持つグラフ 性質 オイラーグラフと準オイラーグラフは 一筆書き可能である オイラーグラフ 全ての頂点の次数が偶数のグラフ 準オイラーグラフ 奇数の次数の頂点を二つだけ含むグラフ 参考 : オイラーの等式, オイラーマクローリン展開, 変分法, 一巡閉路 オイラーグラフ 準オイラーグラフ
オイラー路の判定法 条件 1) 有限グラフ ( 辺の数も頂点の数も ) で連結 (connected) なグラフに限定. において, 1) 始点終点以外の全ての頂点において, 入ってくる辺の数と出て行く辺の数が同じはずなので, その頂点の次数は偶数 2) 始点と終点は次数が奇数である ( 出発のときの出るだけの辺が一つ半端だから. 終点についても同様 ) オイラー路の存在条件 : 1),2) オイラー閉路の存在条件 : 全ての頂点が偶数の次数をもつこと.
オイラー路 ( 例題 ) 例題 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 通り )
ハミルトン路 ( ウィリアム ローワン ハミルトン ( 英国 )) ハミルトン路 : グラフ上の全ての頂点を 1 度だけずつ通る路 ハミルトン閉路 : グラフ上の全ての頂点を 1 度だけずつ通る閉路 ハミルトングラフ : ハミルトン閉路を含むグラフ 準ハミルトングラフ : ハミルトングラフではないがハミルトン路を含むグラフ 与えられたグラフがハミルトン路を含むかどうか判定する問題は NP 困難
ハミルトングラフの性質 1 1. V(G) 3 δ(g) V(G) /2 を満たす単純グラフ G は ハミルトングラフ (Dirac, 1952 年 ) 頂点の数 V(G) 最低次数 δ(g) 単純グラフ G
ハミルトングラフの性質 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
ハミルトングラフの性質 3 1. 完全グラフ K 2n+1 は n 個のハミルトン閉路に分解できる 2. 完全グラフ K 2n は n-1 個のハミルトン閉路と 1 個の 1- 正則な全域部分グラフに分解できる 1- 正則な全域部分グラフ K 5 K 6
演習問題 ( つづき 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) このグラフから何本かの辺を除去して木にするには, 何本を除去すればよいか
解答 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} のいずれかを除去すると木になるが, これ以外の辺を除去しても木にはならない つまり, このグラフに閉路がなくなるように辺を除去しなくてはならない
隣接行列 隣接行列 : 隣接関係を表す行列 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 行の和 = 次数
根つき木の探索法 節点 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) 幅優先探索キュー 深さ優先探索スタック 評価値優先
最短路問題 長さつきネットワーク G=(E,V,W) s 1 50 2 20 15 4 30 例 自宅の最寄り駅から四ッ谷駅までの鉄道の最短時間 ( もしくは最安 ) ルートを求める ( 駅ナビなど ) 80 3 15 5 カーナビを使って現在地から目的地までの最短経路を調べる s t への最短路 一般的な解法 動的計画法 DP 分枝限定法 ダイクストラ法
ダイクストラ法 (Dijkstra Method) 最短経路問題は, やさしい部類の問題であり, 全経路を調べることなく効率的に最短経路が求められるアルゴリズムが存在する. ダイクストラ法の特徴 出発点を 1 つに固定して そこから他のすべての頂点への最短路を求める方法 出発点に近い頂点への最短経路を次々に求める方法
ダイクストラ法の手順 1. 出発点に隣接する頂点の 出発点 - 頂点間の距離を求め 最小の値をもつ頂点にマークを付けて確定する 2. マークのついた頂点に隣接する頂点までの距離を求め この時点で計算されている頂点 ( マークの付いていない ) の距離の中で最小の値をもつ頂点をマークして確定する 3. 以上の操作をすべての頂点にマークがつくまで繰り返すと 各頂点に得られる値が出発点からの最短路となる s 1 50 80 50 2 20 3 15 15 65 4 30 95 80 70 85 V={1, 2, 3, 4, 5} : 頂点集合 N={, 50,, 80, : 隣接行列,, 15, 20,,,, 30, 15,,,, 50,,,, } 5
ダイクストラ法のアルゴリズム 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 に対し http://www.me.sophia.ac.jp/or/lab/ishizuka/oc/spath_00.html
演習問題 ( つづき 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 には辺が何本あるか
解答 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 = [ 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 ] A' = [ 0 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 ] (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 である
ファイル名の書式 学生番号名前課題番号.Doc ( 数字 ) ( 漢字 ) ( 数字 ) 課題番号については, 1. ランダム探索 (TSP) 2. 分枝限定法 ( ナップザック ) 3. 分枝限定法 (TSP) 4. ダイクストラ法 ( 最短経路 ) ボーナス点
レポートの書き方 表紙 : 学生番号名前課題番号, 日時課題内容方法論実現方法 ( プログラム 解説 ) 解析結果考察感想