最適化手法 第 回 工学部計数工学科 定兼邦彦 http://researchmap.jp/sada/resources/
前回の補足 グラフのある点の隣接点をリストで表現すると説明したが, 単に隣接点の集合を持っていると思ってよい. 互いに素な集合のデータ構造でも, 単なる集合と思ってよい.
8 3 4 3 3 4 3 4 E v 重み 3 8 3 4 4 3 {{,},{3,8}} {{3,},{4,}} {{4,},{,}} {{,3}} {} 領域計算量 O(n+m) 集合による表現
互いに素な集合のためのデータ構造 互いに素な動的集合の集合 S={S, S,, S k } を扱う make_set(x): 唯一の要素 x をもつ新しい集合を作る x がすでに別の集合に含まれていてはいけない union(x, y): x と y を含む集合 S x と S y を合併し, それらの和集合を作る. 元の集合は S から取り除く. find_set(x): x を含む集合の代表元へのポインタを返す make_set の回数 n と全操作の総実行回数 m で評価する. union の回数は n 以下 4
集合による表現 互いに素な動的集合の集合 S={S, S,, S k } を扱う make_set(x): S x = {(x, x)} とする find_set(x): x を含むペア (r, x) の r を返す union(x, y): r = find_set(x), s = find_set(y) とする S s の方が要素数が少ないとき, S s の各要素 (s, z) を (r, z) に置き換え, S r に入れる. S s は削除する.
最短路問題 有向グラフ G = (V, E) を考える V: 節点集合, 節点数 n E: 枝集合, 枝数 m グラフ G の各枝 (i,j) E は長さ a ij を持つ ある節点 s V から別の節点 t V への路の中で, 最も長さの短いものを見つける問題を最短路問題という 8 3 4 3 6
問題のバリエーション 単一点対最短路問題 s から t への最短路を求める 単一始点最短路問題 (single-source shortestpaths problem) s からグラフの各点までの最短路を全て求める 全点対最短路問題 (all-pairs shortest-paths problem) 全ての頂点対 s, t について最短路を求める
LP による定式化 単一点対最短路問題を LP で表す 目的関数 : 制約条件 : ( i, j) E ij { j ( i, j) E} x ij x c ij x ij { j ( (( i, 最小 x ji j, i) E} j) E) i i s t i s, t xijは整数 x ij = のとき辺 (i,j) が最短路に含まれる 8 3 4 3 8
注 : この定式化では変数 x ij は整数に制限しているため,LP にはなっていない ただし, 整数条件を外して LP を解くと, 解は必ず整数解になる (total unimodularity) 略証 : もし < x ij < なら, 点 i で経路が つに分かれてどこかで合流している. つの経路のうち短い方を使う方が目的関数が小さくなるので, 経路が分かれない方が解になる. 9
単一始点最短路問題の LP による定式化 目的関数 : 制約条件 : ( i, j) E ij { j ( i, j) E} x ij x c ij x ij x は整数 ij x ij > のとき辺 (i,j) が最短路に含まれる { j ( (( i, 最小 x ji j, i) E} j) 4 E) 8 n 3 i i s s 4 3
この場合も x ij の整数条件を外して LP を解けば整数解が求まる. LP は多項式時間で解けるが, より高速なアルゴリズムを考える
Bellman-Ford アルゴリズム 単一始点最短路問題を解くアルゴリズム 枝の長さが負でも動く ただし, 長さが負の閉路は無いとする 長さが負の閉路があるときはそれを検出する 時間計算量 : O(nm)
長さが負の閉路 点 から点 への最短路は? 3 だと長さ 8 3 4 3 だと長さ 8 3 4 3 4 3 だと長さ 長さが負の閉路があると, 最短路長が - になる - - 4 3 8 3 3
長さが非負の閉路 ある経路が長さが非負の閉路を含む場合, それを取り除くと経路の長さは減る ( か同じ ) 最短路を考えるときは, 閉路は無いとして良い 閉路を含まない経路の長さは n 以下 4
Bellman-Ford(G, w, s). for each v V(G). d[v], [v] NIL 3. d[s] 4. for i to n. for each (u, v) E(G) 6. if d[v] > d[u] + w(u, v). d[v] d[u] + w(u, v) 8. [v] u 9. for each (u, v) E(G). if d[v] > d[u] + w(u, v) return false // 閉路がある. return true
初期状態 6 - -3 s 8 9-4 6
i = 6 6 - -3 s 8 9-4
i = 6 6 - -3 4 s 8 9-4 8
i = 3 6 - -3 4 s 8 9-4 9
i = 4 = n ( 終わり ) 6 - -3 4 s 8 9-4 -
補題 : アルゴリズムの i 回目のループが終了したとき, 各 d[v] の値は (s から i 本以下の辺を通って v に到達する最短経路の長さ ) となっている. 証明 : 帰納法で示す.i =, つまりループに入る前は,d[s] =, それ以外の点では d[v] = なので成り立つ.i の時成り立つと仮定する.i+ 回目のループでは, for each (u, v) E(G) if d[v] > d[u] + w(u, v) d[v] d[u] + w(u, v) と更新する. 点 v について考えると,v に入ってくる枝 (u, v) に対し, 帰納法の仮定より d[u] は i 本以下の辺を通る s から u への最短路長になっている.
i+ 回目のループでは v に入る全ての辺に対してこの処理を行うため, ループの終わりでは d[v] は i+ 本以下の辺を通る s から v への最短経路の長さになる.
補題 : G が s から到達可能な負の長さの閉路を含んでいないとき, アルゴリズム終了時に全ての点 v V(G) に対し d[v] は最短経路長と等しい. 証明 : v が s から到達不可能のとき, 最短経路長は で,d[v] と等しいため成り立つ. v が s から到達可能のとき,v までの経路上には仮定より負の長さの閉路は無い. つまり最短路長は n 以下である. アルゴリズムはループを n 回繰り返すため, 補題 より終了時には d[v] は辺を n 本以下使う経路の中で最短のものの長さとなっている. 3 つまりそれは最短路長である.
定理 : Bellman-Ford アルゴリズムは, G が s から到達可能な負の長さの閉路を含んでいないとき true を返し,d[v] は s から v への最短路長である. G が s から到達可能な負の長さの閉路を含むときは,false を返す. 証明 : G が s から到達可能な負の長さの閉路を含んでいないとき, 補題 より d[v] は s から v への最短路長である. このとき全ての辺 (u, v) に対し d[v] d[u] + w(u, v) が成り立つ. つまりアルゴリズムは true を返す. 4
G が s から到達可能な負の長さの閉路を含むとき, その つを v, v,, v k とする (v = v k ). 背理法で証明するために, アルゴリズムが true を返すと仮定する. つまり, d[v i ] d[v i- ] + w(v i-, v i ) (i =,,,k) が成り立つ. 閉路上でこれを足すと k i d k v i d vi w( vi, vi ) i v = v k であるため,d[] の和は両辺で等しい. つまり k i w( v i, v i ) これは負の長さの閉路であることに矛盾.
ダイクストラ (Dijkstra) 法 辺の長さが全て非負の場合に使えるアルゴリズム Bellman-ford よりも速い 単純な実装でも O(n ) 時間 (n < m) データ構造を工夫すると O(m log n) 時間 さらに複雑なものを用いると O(m + n log n) 時間 6
Dijkstra(G, w, s). for each v V(G). d[v], [v] NIL 3. d[s] 4. S, Q V(G). while Q 6. Q の中で d が最小の点 u を取り出す. S S {u} 8. for each (u, v) E(G) // (u の隣接点 ) 9. if d[v] > d[u] + w(u, v). d[v] d[u] + w(u, v). [v] u
初期状態 s 3 9 4 6 8
s 3 9 4 6 9
s 8 3 9 4 4 6 3
s 8 3 9 4 3 6 3
s 8 3 9 4 9 6 3
s 8 3 9 4 9 6 33
最適性の原理 節点 s から t への最短路 P が得られているとする 路 P に含まれる節点を つ任意に選び, r とする 路 P は s から r までの部分 P と, r から t への部分 P に分割できる. このとき,P は s から r への最短路で,P は r から t への最短路となる もし P より短い s から r への路 P が存在するなら, P と P をつないだ路は P より短くなる このような性質を最適性の原理と呼ぶ P r P s P t 34
アルゴリズムの正当性の証明 ダイクストラ法で,S は出発点 s からの最短路の長さがわかっている節点の集合であることを確認 以下のことを帰納法で示す 全ての i に対し, d(i) = [S に含まれる節点のみを経由して s から i に至る最短路の長さ ] () (S に含まれる節点のみを経由するのでは到達できない場合は d(i) = ) i S ならば,d(i) = [s から i への最短路の長さ ] 3
[ 反復 ] 終了後 S = {s}, d(s) = S の点 s では,s から s への最短距離は で,d(s) と等しい S の点から 本の枝で到達できる Q の点では d(i) = [S に含まれる節点のみを経由して s から i に至る最短路の長さ ] が成り立つ それ以外の点では d(i) = で, 命題は成立 36
帰納法の仮定 : ある反復に入った時点で命題成立 ステップ 6 で u が選ばれたときに,u に対し d(u) = [S に含まれる節点のみを経由して s から u に至る最短路の長さ ] = [s から u への最短路の長さ ] () それ以外の点に対して () が成り立つことを示す () を背理法で示す.s から u への最短路を P* とし, その長さが d(u) と異なるとする アルゴリズムの構成法より, 各節点 i に対し,d(i) は s から i へのある路の長さを表しているので, 上の仮定は d(u) > [ 路 P* の長さ ] を意味する 3
u Q なので,() より,s から u への真の最短路 P* は, 途中で Q の点を少なくとも つ経由する P* において初めて現れる Q の点を w とすると, * * P* はとに分解できる P P 最適性の原理より, * P は s から w への最短路 * P は S の点のみを経由しているので,() より * d(w) = [ 路 P の長さ ] が言える S Q p(u) u * P s * P w 38
各枝の長さは非負なので, * [ 路 P* の長さ ] [ 路の長さ ] P よって,d(u) > d(w) (d(u) > [ 路 P* の長さ ] より ) ところが, d( u) mind ( i) i Q と wq より d(u) d(w) となり, 矛盾 よって,d(u) は s から u への最短路の長さに等しい () より, その路は S の節点のみを経由するので, () が成り立つ S Q p(u) u * P s * P w 39
反復が終了した時点で () が保たれていることを示す 反復終了時の S を S S {u} と書く アルゴリズムのステップ を実行したとき j Q d(v) を示す S + に含まれる節点のみを経由して s から v に至る最短路は次の 3 つの場合が考えられる (a) u を経由しない, つまり S の節点のみを経由 (b) v に到達する直前に u を経由 [S + に含まれる節点のみを経由して s から v に至る最短路の長さ ] (c) u を経由し, その後さらに S の節点をいくつか通って 4 v に到達
(c) はありえない. なぜなら, そのような路が最短路の場合,v の直前の節点を w とすると, 最適性の原理より, その路の w までの部分は s から w の最短路 w はそれ以前の反復で S に入っているので,S の節点のみを経由する s から w への最短路が存在するはず よって,s から v への最短路は (a) か (b) のどちらか ステップ で,d(v) > d(u) + w(u, v) ならば d(v) を d(u) + w(u, v) で置き換えるが, これは (a) よりも (b) の方が路が短いときに最短路を置き換えることに対応 以上より証明できた. 4
時間計算量の解析 while ループの 回ごとに Q の要素数は 減る ループの回数は n 各ループでは d[u] の最小値を求めるのに O(n) 時間 u から出ている各枝 (u, v) の処理に O() 時間 枝の処理時間の合計は O(m) 全体の時間は O(n + m) = O(n ) 4
計算量の改良 d[u] の最小値を求める操作に無駄がある. ヒープと呼ばれるデータ構造を使うと, 全体の計算量は O(m log n) フィボナッチヒープを使うと, O(m + n log n) 43