ネットワーク理論 Text. Part 3 pp. 57-104 最短路問題 pp.58-84 最大流問題 pp.85-94 Ford法,双対問題とポテンシャル，Bellman方程式とBellman-Ford法 負の費用をもつ閉路がある場合，閉路を含まない場合 最大流問題 pp.85-94 最小費用流問題 pp.95-104 1

大名の例題 飛脚に払う費用 （単位は両） 終点 始点 2

最短路問題（定義） 点集合 V 枝集合 E 有向グラフ G=(V,E) 枝の費用 c: E → R+ 目的： 始点sから終点tまでの最小費用のパス c は枝集合Ｅから 非負の実数全体への写像 点とそれに接続する 枝が交互に並んだもの 最短路 3

Ford法（アイディア） 費用=10（両） 宿場１ 富士山 氷の価格=0（両） 氷の価格=9（両） 氷を運びますか？ 氷の価格=10（両） 氷の価格=11（両） 4

アイディアの形式化 小売価格＝ポテンシャル 費用=cvw 点w 点v 氷の価格=yv（両） 氷の価格= yw（両） 氷を運びますか？ 点のポテンシャル y : V→ R ywがyv＋cvw以上なら 飛脚は氷を運ぶ！ y は点集合 V から 実数全体への写像 5

「小売価格の見直し」操作 費用=10（両） 宿場１ 富士山 氷の価格=0（両） 小売価格が 適正でない！ 氷の価格=13（両） 小売価格の 氷の価格=10（両） 6

Ford法（飛脚組合バージョン） 富士山の氷の価格=0；他の宿場町の氷の価格＝∞ while 小売価格が適正でなければ．．． do （wにおける）価格が適正でない枝 vw に対して「小売価格の見直し」 7

解いてみよう！（１） 8

解いてみよう！(２） ∞ ∞ ∞ ∞ 9

解いてみよう！(３） ∞ ∞ 価格が適正でない ∞ ∞→5 10

解いてみよう！(４） ∞ ∞→10 価格が適正でない ∞ 5 11

解いてみよう！(５） ∞ 10→8 価格が適正でない ∞ 5 12

解いてみよう！(６） ∞ 8 価格が適正でない ∞→7 5 13

解いてみよう！(７） ∞→13 8 価格が適正でない 7 5 14

解いてみよう！(８） 13→9 8 価格が適正でない 7 5 15

解いてみよう！(９） 9 8 全ての価格が 適正になった 7 5 16

ポテンシャルの実行不能，実行可能 小売価格＝ポテンシャル ポテンシャルが実行不能 （小売価格が適正でない） ポテンシャルが実行可能 （小売価格が適正） 17

Ford法 ys:=0， yv :＝∞, While ポテンシャル yが実行不能 do 集合の差演算 ys:=0， yv :＝∞, While ポテンシャル yが実行不能 do yw>yv+cvwを満たす枝を見つけて yw:=yv+cvw 18

双対問題とポテンシャル -まずは線形計画として定式化- 変数 xvw: 最短路（最適パス）が枝vwを使うなら１，それ以外なら0 例：始点 s に対して， xs1=0, xs2=1　（８ページ目のスライド参照） xがパスを表すためには．．． 始点 s から飛脚が１人出ていく！ xs1+xs2=1 19

線形計画として定式化２ xがパスを表すためには．．． 点1に飛脚が入ってきたら出ていかなければならない！ xs1+x21 -x12-x1t =0 点2に飛脚が入ってきたら出ていかなければならない！ xs2+x12 –x21-x23 =0 点3に飛脚が入ってきたら出ていかなければならない！ x23-x3t =0 終点tには飛脚が入ってくる！ x1t+x3t =１ 20

線形計画として定式化３ パスに含まれている枝の費用の合計は最小化 最小化10xs1+5xs2+2x12+x1t+3x21+2x23+6x3t 条件 -xs1- xs2 =-1 xs1 - x12-x1t+ x21 =0 xs2+ x12 - x21- x23 =0 x23- x3t =0 x1t + x3t =1 21

双対問題を作ってみよう！ 絶対に失敗しない方法 (Lagrange緩和を用いる！） まず，主問題のそれぞれの制約式に対応する双対変数を用意 22

双対問題を作ってみよう！ 最小化10xs1+5xs2+2x12+x1t+3x21+2x23+6x3t 条件 -xs1- xs2 =-1 xs1 - x12-x1t+ x21 =0 xs2+ x12 - x21- x23 =0 x23- x3t =0 x1t + x3t =1 ×ys ×y1 ×y2 ×y3 ×yt (xs1+xs2-1)×ys (-xs1+x12+x1t-x21)×y1 (-xs2-x12+x21+x23)×y2 (-x23+x3t)×y3 (-x1t-x3t+1)×yt 任意の実数 （負でも良い） =0 23

双対問題を作ってみよう！ 最小化 10xs1+5xs2+2x12+x1t+3x21+2x23+6x3t +(xs1+xs2-1)ys+(-xs1+x12+x1t-x21)y1 +(-xs2-x12+x21+x23)y2+(-x23+x3t)y3 +(-x1t-x3t+1)yt 条件 主問題と同じ =0 任意の実数 この部分は0 24

双対問題を作ってみよう！ 最小化 yt-ys +(10+ys-y1)xs1+(5+ys-y2)xs2+(2+y1-y2)x12 +(1+y1-yt)x1t+(3+y2-y1)x21 +(2+y2-y3)x23+(6+y3-yt)x3t 条件 主問題と同じ 25

双対問題を作ってみよう！ 目的関数に加えた制約を全て緩和 下界を与える 最小化 yt-ys+(10+ys-y1)xs1+(5+ys-y2)xs2+(2+y1-y2)x12 +(1+y1-yt)x1t+(3+y2-y1)x21+(2+y2-y3)x23+(6+y3-yt)x3t 条件 xは0以上 最大化 0以上でないと 発散してしまう 最小化 最適値 下界（目的関数に加えた項の 合計は０，式を緩和したので） 26

双対問題 ポテンシャルが実行可能である条件 小売価格が適正 双対問題 最大化 yt-ys 条件 27

双対問題の意味合いを考えてみよう（ポテンシャルと双対変数の関係） 双対変数yは宿場町での氷の小売価格（ポテンシャル）を表す． 双対問題の目的関数は，江戸と富士山の小売の価格（ポテンシャル）の差の最大化を表す． 双対問題の制約式は，小売価格が適正（ポテンシャルが実行可能）であることを表す． 28

Bellman方程式とBellman-Ford法 -双対問題を眺めてみよう！- よりy1=min{ys+10,y2+3}である． 同様に y2=min{ys+5,y1+2}, y3=min{y2+2}, yt=min{y1+1,y3+6} 29

Bellman方程式 つまり次式を満たすyを求めれば良い． Bellman方程式 30

Bellman方程式を解こう１ y1=min{10,y2+3} y1=min{ys+10,y2+3} y2=min{5,y1+2} ys=0（富士山sの小売価格は０） y1=min{10,y2+3} y2=min{5,y1+2} y3=y2+2 yt=min{y1+1,y3+6} y1=min{ys+10,y2+3} y2=min{ys+5,y1+2} y3=min{y2+2} yt=min{y1+1,y3+6} 31

Bellman方程式を解こう２ y2=min{5,min{10,y2+3}+2} 整理して y2=min{5,min{12,y2+5}} y1=min{10,y2+3}を y2=min{5,y1+2} に代入 y2=min{5,min{10,y2+3}+2} 整理して y2=min{5,min{12,y2+5}} もっと整理して y2=min{5,12,y2+5}；よって y2 =5 32

Bellman方程式を解こう３ y2 =5 がわかったので．．． y1=min{10,y2+3}より y1=min{10,5+3} =8 y3=y2+2 より y3=5+2=7 yt=min{y1+1,y3+6}より yt= min{8+1,7+6}=9 より系統的な方法はないものか？ （手計算でなくコンピュータでもできるように！） 33

Bellman方程式（修正版） yv(k)=始点sから，たかだかk本の枝を経由し， 点vに至る最適パスの費用 点wにk+1本の枝を経由してくるときの費用 点vにk本の枝を経由してくるときの 費用にvからwへ移動の費用を加えたもの 点wにk本の枝を経由 してくるときの費用 34

Bellman方程式（修正版）をもとにしたFord法 -Bellman-Ford法- k＝０のときは簡単！ ys(0)=0（始点 s までは枝 0 本で費用０） yv(0)=∞（s以外の点vには，枝 0 本では行けない） これを初期条件として．．． k=1,2,3,4（点の数から１を減じた回数だけ；なぜか？） の順にy(k) を計算する． 35

Bellman-Ford法の適用例 点 k=0 k=1 k=2 k=3 k=4 s 1 ∞ 2 3 t 表の値はyv(k) 8 10 8 8 1 ∞ 2 3 t 8 10 8 8 5 5 5 5 最適値 7 ∞ 7 7 9 ∞ 11 9 36

Bellman-Ford法 ys(0):=0, yv(0):=∞, for k=0 to n-1 do yw(k+1):=yw(k) ,∀w ∈V for all do if yv(k)+cvw<yw(k+1) then yw(k+1):=yv(k)+cvw 37

Bellman-Ford法の適用例 最適パスを記憶する場合 sからきたことを表す 点 k=0 pr k=1 pr k=2 pr k=3 pr k=4 pr s 1 ∞ 10 s 8 2 2 5 s 5 s 3 7 2 t 11 1 9 1 表の値はyv(k)と直前の点pr（Previousの略） 38

Bellman-Ford法の適用例 点 k=0 k=1 pr k=2 pr k=3 pr k=4 pr s 1 ∞ 2 3 t 1 ∞ 2 3 t sからきたことを表す 10 s 8 2 8 2 8 2 5 s 5 s 5 s 5 s 最適値 ∞ 7 2 7 2 7 2 ∞ 9 1 11 1 9 1 39

最短路木 （最適パスの情報を含んだ木） Bellman-Ford法の表を後からたどることにより， 最短路木を作成 1 t s 2 3 40

演習問題１ Aから各点への最短路をFord法で求めてみよう． Aから各点への最短路をBellman-Ford法で求めてみよう． B E A 5 4 注：無向グラフなので A->B,B->Ａの両方向に 枝がある有向グラフと みなして解くこと！ 4 3 C 9 F 3 3 10 D 4 41

演習問題２ 下のネットワークにおいて，sからtへの最短路を Bellman-Ford法で求めることができるかな？ （オプション課題） 42

ネットワーク理論 Text. Part 3 pp. 57-104 最短路問題 pp.58-84 最大流問題 pp.85-94 Ford法,双対問題とポテンシャル，Bellman方程式とBemmlan-Ford法 負の費用をもつ閉路がある場合，閉路を含まない場合 最大流問題 pp.85-94 最小費用流問題 pp.95-104 43

大名の例題 飛脚に払う費用 （単位は両） 終点 始点 Ford法を適用してみよう 44

Ford法の適用 ∞ ∞ 1 1 t 10 -5 s 6 3 2 5 2 3 2 ∞ ∞ 45

Ford法の適用 ∞→10 ∞ 1 1 t 10 -5 s 6 3 2 5 2 3 2 ∞ ∞ 46

Ford法の適用 10 ∞ 1 1 t 10 -5 s 6 3 2 5 2 3 2 ∞ ∞→5 47

Ford法の適用 10 ∞ 1 1 t 10 -5 s 6 3 2 5 2 3 2 ∞→7 5 48

Ford法の適用 10→2 ∞ 1 1 t 10 -5 s 6 3 2 5 2 3 2 7 5 49

Ford法の適用 1 t s 2 3 10→2→1→ ∞ 1 10 -5 6 3 2 5 終わらない！ 2 5→4→3→ 7→6→5→ -5 s 6 3 2 5 2 3 終わらない！ 2 5→4→3→ 7→6→5→ 合計費用が負の閉路 （＝負の閉路） 50

最短路問題 （枝の費用が負を許す場合） （下線を引いた部分が改訂箇所） 点集合 V 枝集合 E 有向グラフ G=(V,E) 枝の費用 c: E → R （Rは実数全体の集合；負でも良い！） 目的： 始点sから終点tまでの最小費用のパス あるいは負の閉路を見つける 51

Ford法は失敗した！ Bellman-Ford法はどうだろう？（復習） yv(k)=始点sから，たかだかk本の枝を経由し， 点vに至る最適パスの費用 Bellman-Ford法を言葉で書くと．．． k＝０のときを初期条件として．．． k=1,2,3,4 （点の数は5個;最適パスの枝は最大でも4本だから！） の順にyv(k)を計算する． 52

Bellman-Ford法のちょっとした変形（アイディア） 最適パスは枝をたかだか４本使う． ５本使ったときに，最適パスの費用yv(k)が（４本使ったときより）小さくなったら，負の閉路がある！ 53

改訂したBellman-Ford法 （負の費用をもつ枝をもつ 最短路問題に対するアルゴリズム） k＝０のときを初期条件として， k=1,2,3,4,5 まで yv(k)を計算し，yv(4) > yv(5)になる点 v があるなら「負の閉路がある」といって終了 それ以外なら， yｔ(4)が最適パスの費用 54

Bellman-Ford法（擬似コード） （下線を引いたのが改訂箇所） ys(0):=0, yv(0):=∞, pred(v):=empty, for k=0 to n do yw(k+1):=yw(k) ,∀w ∈V for all do if yv(k)+cvw<yw(k) then yw(k+1):=yv(k)+cvw pred(w):=v 55

Bellman-Ford法を適用してみよう 表の値はyv(k)と直前の点pr（Previousの略） 点 k=0 pr k=1 pr k=2 pr k=3 pr k=4 pr k=5 pr s 10 s 5 ∞ 8 2 5 s 7 11 1 2 3 5 s 7 9 1 2 3 4 1 7 2 3 4 1 6 v=3に対して yv(4) >yv(5) 1 ∞ 2 ∞ ∞ 3 ∞ t 56

最短路木の作成 Bellman-Ford法の表を後からたどることにより， 最短路木を作成 点 … k=5 pr s 1 2 3 2 4 1 3 6 2 t 3 1 1 t tの直前は1 s 2の直前は1 1の直前は3 2 3 3の直前は2 57

最短路木の作成 Bellman-Ford法の表を後からたどることにより， 最短路木を作成 点 … k=5 pr s 1 2 3 2 4 1 3 6 2 t 3 1 1 t 負の閉路 発見 s 2 3 58

通貨の変換によって儲けよう ￥ 1ドル＝112.44円 ×112.44 ×0.007689 1円＝0.007689ユーロ ＄ ユーロ 1ユーロ＝1.1567ドル ×1.1567 1×112.44×0.007689×1.1567＝1.000026326772 投資額が大きい機関投資家なら手数料が無視できる ので，ちょっと儲かる． 59

2001年1月19日の為替レート ￥ US＄ EUR ￡ ＤＭ FFr Ａ＄ HK＄ Ｂ Ｗ 60 日本円 100 0.8400 0.8849 0.5617 1.7304 5.8038 1.4663 6.4267 35.587 1077.6 米ドル 119.05 1 1.0535 0.6687 2.0600 6.9095 1.7456 7.6510 42.367 1282.9 ユーロ 113.01 0.9493 0.6348 1.9555 6.5589 1.6570 7.2629 40.217 1217.8 英ポンド 178.04 1.4955 1.5754 3.0808 10.333 2.6106 11.442 63.359 1918.5 ドイツマルク 57.790 0.4854 0.5114 0.3246 3.3540 0.8474 3.7140 20.566 622.74 仏フラン 17.230 0.1447 0.1525 0.0968 0.2982 0.2526 1.1073 6.1317 185.67 豪ドル 68.200 0.5729 0.6035 0.3831 1.1801 3.9582 4.3830 24.270 734.92 香港ドル 15.560 0.1307 0.1377 0.0874 0.2693 0.9031 0.2282 5.5374 167.67 タイバーツ 2.8100 0.0236 0.0249 0.0158 0.0486 0.1631 0.0412 0.1806 30.280 韓国ウォン 9.2800 0.0780 0.0821 0.0521 0.1606 0.5386 0.1361 0.5964 3.3025 60

通貨の変換によって儲けよう 通貨vから通貨wへの変換レートを Rvk,v1 とする． 通貨を点としたグラフで，閉路 v1->v2->…vk->v1で Rv1,v2× Rv2,v3×‥‥ Rvk-1,vk× Rvk,v1＞1 となるものを求める問題． 枝vw上の費用cvwをcvw=-log Rvwとすると -(logRv1,v2+logRv2,v3+‥‥+logRvk-1,vk+logRvk,v1)= -log(Rv1,v2×Rv2,v3×‥‥×Rvk-1,vk×Rvk,v1) < 0 なのでグラフ上で負の閉路を求める問題に帰着される． 61

通貨の変換によって儲けよう 注意！個人投資家がやっても，手数料があるので儲からない． （日本の）銀行だと１＄あたり1円の手数料がかかる． 一度に変換する額が大きすぎると，為替レート自身が動いてしまう． -> 次々回にやる最小費用流を用いて，一度に変換する量に制限（容量）をつける． 62

最長路問題 最長路問題(longest path problem) 有効グラフ G=(V,E) 同じ点を2回以上 枝上の距離関数 d:E→R+ 始点から終点までの単純パスで， パスに含まれる枝の距離の合計が最大のものを求めよ 同じ点を2回以上 通らないパス 63

大名の例題 ストライキ 終点 始点 64

大名の例題 （閉路がない場合） 1 t s 2 3 1 10 -5 6 3 5 2 閉路がなくなったので，枝の費用が負でも 負の閉路ができる心配はない！ 65

閉路がないグラフ上の問題を 解くときの基本ツール -トポロジカル・ソート- s 2 3 1 t トポロジカル・ソート （topological sort;位相の情報を用いた並べ替えの意） 66

並べ替えのアルゴリズム（ソーティング）（復習？） 挿入ソート（insertion sort） やってみよう！ 67

並べ替え(ソーティング) 問題の入力 出力 データの個数nおよびデータのキーA[j](j=1,・・・,n) 挿入ソート O(n2) マージソート O(n logn) クイックソート O(n2) 平均的にはO(n logn) ヒープソート O(n logn) 良いアルゴリズム 68

挿入ソート(Insertion sort) 1 jを２からnまで１ずつ増やす 2 A[1..j-1]まではちゃんと並べられている 3 A[j]をA[1..j]の中の適切な場所に挿入する j 1 2 3 4 A[j] 3 2 4 1 A[1..1]はOK A[j] 2 3 4 1 A[1..2]はOK A[j] 2 3 4 1 A[1..3]はOK A[j] 1 2 3 4 A[1..4]はOK 69

挿入ソート(Insertion sort) 「A[j]をA[1..j]の中の適切な場所に挿入する」の詳細化 key =A[j] i=j-1から1まで，key<A[i]になるまでA[i]を右にずらす key（A[j])をずらした位置に入れる A[j] 2 3 4 1 A[1..3]はOK keyに一時保存 2 3 4 A[j] 1 2 3 4 A[1..4]はOK 70

挿入ソート(Insertion sort) 1 jを２からnまで１ずつ増やす 2 key = A[j] 3 iをj-1からA[i]>keyまたはi=0になるまで１ずつ減らす 4 A[i+1]=A[i] 5 A[i+1] =key 最悪の場合の計算量：　O(n2) n2　回かかる例： A[j] 5 4 3 2 1 A[j] 1 2 4 3 5 71

トポロジカル・ソート 1 t s 2 3 言葉の準備（復習！覚えているかな？） 入次数：点に入ってくる枝の数 出次数：点から出て行く枝の数 入次数：0 出次数：2 入次数：2 出次数：0 入次数：1 出次数：2 入次数：3 出次数：1 入次数：1 出次数：2 s 2 3 72

トポロジカル・ソート While グラフに点がある do 入次数＝０の点を見つける （必ず一つは見つかる） その点とその点に入ってくる枝をグラフから消す 点を消した順に左から並べる やってみよう 73

トポロジカル・ソート 2 3 1 t 入次数が0なので この点と この点から出る枝を消す s 1 1 2 3 74

トポロジカル・ソート 2 3 1 t s 1 1 2 3 75

トポロジカル・ソート 2 2 1 t 入次数の変化する点がある 1 2 3 s 76

トポロジカル・ソート 2 2 1 t 入次数が0なので この点と この点から出る枝を消す 1 2 3 s 77

トポロジカル・ソート 2 2 1 t 1 2 3 s 78

トポロジカル・ソート 2 1 1 t 入次数の変化する点がある 3 s 2 79

トポロジカル・ソート 2 1 1 t 入次数が0なので この点と この点から出る枝を消す 3 s 2 80

トポロジカル・ソート 2 1 1 t 3 s 2 81

トポロジカル・ソート 1 1 t 入次数の変化する点がある s 2 3 82

トポロジカル・ソート 1 1 t 入次数が0なので この点と この点から出る枝を消す s 2 3 83

トポロジカル・ソート 1 1 t s 2 3 84

トポロジカル・ソート 1 t s 2 3 1 85

トポロジカル・ソート s 2 3 1 t 86

トポロジカル・ソートの擬似コード 点vの入次数をindegree(v)と書く indegreeの初期設定 indegree(v):=0, for all do for all do indegree(w):=indegree(w)+1 87

トポロジカル・ソートの擬似コード 入次数が0である点のリストをLISTと書く LISTの初期設定 LIST:=empty for all do if indegree(v)=0 then 88

トポロジカル・ソートの擬似コード トポロジカル・ソート indegreeの初期設定 LISTの初期設定 while LISTが空でない do LISTから適当に点vを選択し，vを左詰めで並べる for all do indegree(w):=indegree(w)-1 if indegree(w)=0 then 89

Ford法の高速化（アイデア） トポロジカル・ソートを用いるとFord法を高速化できる． なぜか？ トポロジカル・ソートされた順にポテンシャル を更新すれば，あともどりがなくなる （つまり，ポテンシャルは１回だけ更新すれば良い）から やってみよう 90

大名の例題 1 1 t 10 -5 s 6 3 5 2 3 2 トポロジカル・ソートすると 91

Ford法（高速化版） 3 6 ∞ ∞ ∞ ∞ s 2 3 1 t 1 5 2 -5 10 92

Ford法（高速化版） s 2 3 1 t 3 6 ∞→5 ∞ ∞→10 ∞ 1 5 2 -5 10 点v（上の場合はs）の走査（scan） ∞→5 ∞ ∞→10 ∞ s 2 3 1 t 1 5 2 -5 10 点v（上の場合はs）の走査（scan） for all do if yv+cvw<yw then yw:=yv+cvw 93

Ford法（高速化版） 3 6 5 ∞→7 10→8 ∞ s 2 3 1 t 1 5 2 -5 10 94

Ford法（高速化版） 3 6 5 7 8→2 ∞→13 s 2 3 1 t 1 5 2 -5 10 95

Ford法（高速化版） 3 6 5 7 2 13→3 s 2 3 1 t 1 5 2 -5 10 96

Ford法（高速化版） 最短路が 求まった 3 6 5 7 2 3 s 2 3 1 t 1 5 2 -5 10 ちゃんと書くと 97

Ford法（高速化版） ちゃんと書くと 宿場町vから直接 行ける宿場町の 価格を一度に見直す！ 点vの走査 for all do if yv+cvw<yw then yw:=yv+cvw 閉路を含まないグラフに対するFord法 グラフをトポロジカル・ソート（その順にv1,v2,…) ポテンシャルyの初期設定 for i=1 to n do 点viの走査 98

航空機を早く離陸させよう （閉路なし最短路問題の一例） 飛行機の着陸から離陸まで最低何分かかるかな？ 最短路問題に変形してみよう 99

航空機を早く離陸させよう 点ではなく枝に長さを持つ ネットワークに変形 →閉路のない最短路問題に ダミーの枝 100

航空機を早く離陸させよう 実際に計算してみよう 着陸から離陸までの時間を，Ford法（高速化版）の適用によって求めてみよう！（OHP利用） 101

ダイクストラ法 枝の費用が非負のネットワークに対する 最短路問題の代表的なアルゴリズム だいたいの教科書にはこれが最初に 書いてある． 102

ダイクストラ法（アイディア） 点の走査順序を「点が一度走査されたら、それ以降 走査する必要がない」ことが肝要 枝の費用が非負ならば，そのようにできる ポテンシャルが最小の点を走査すれば， その点はその後走査する必要はない（なぜか？） やってみよう 103

ダイクストラ法（やってみよう） ∞ ∞ 1 1 t 10 ポテンシャル 最小の点を走査 s 6 3 2 5 2 3 2 ∞ ∞ 104

ダイクストラ法（やってみよう） ∞→10 ∞ 1 1 t 10 s 6 3 2 5 2 3 2 ∞ ∞→5 105

ダイクストラ法（やってみよう） 1 t s 2 3 10 ∞ 1 10 ポテンシャル 最小の点を走査 6 3 2 5 2 ∞ 走査済み 5 s 6 3 2 5 2 3 2 ∞ 走査済み 5 106

ダイクストラ法（やってみよう） 10→8 ∞ 1 1 t 10 s 6 3 2 5 2 3 2 ∞→7 5 107

ダイクストラ法（やってみよう） 8 ∞ 1 1 t 10 ポテンシャル 最小の点を走査 s 6 3 2 5 2 3 2 7 5 108

ダイクストラ法（やってみよう） 8 ∞→13 1 1 t 10 s 6 3 2 5 2 3 2 7 5 109

ダイクストラ法（やってみよう） 8 13 1 1 t 10 ポテンシャル 最小の点を走査 s 6 3 2 5 2 3 2 7 5 110

ダイクストラ法（やってみよう） 8 13→9 1 1 t 10 s 6 3 2 5 2 3 2 7 5 111

ダイクストラ法（やってみよう） 8 9 1 1 t 10 終了 s 6 3 2 5 2 3 2 7 5 112

ダイクストラ法（きちんと書くと） Dijkstra法 ポテンシャルyの初期設定 S:=V while Sが空でないならば do yvが最小の点　　　を選択 S:=S＼{v} 点vの走査 113

演習問題１ Aから各点への最短路をDijkstra法で求めてみよう． B E A 5 4 注：無向グラフなので A->B,B->Ａの両方向に 枝がある有向グラフと みなして解くこと！ 4 3 C 9 F 3 3 10 D 4 114

演習問題２ 自分の家（下宿もしくは実家）から大学までの交通機関を表すネットワークを作成し，最短時間のパスおよび最小費用を求めよ． 注：移動時間や費用の計算には，「駅前探検クラブ」http://ekitan.com/ などを利用して良いが，最短路は自分で計算して求めること． 115

最短路問題をGurobiで解こう！ 流通最適化工学 補助資料

単純な実装 キー（枝）のリスト， 費用を表す辞書 cost を返す． from gurobipy import * E, cost = multidict( {(0,1):10, (0,2):5, (1,2):2, (1,4):1, (2,1):3, (2,3):2, (3,4):6} ) V=range(5) print "E=",E print "cost=",cost E= [(0, 1), (1, 2), (2, 3), (1, 4), (3, 4), (0, 2), (2, 1)] cost= {(0, 1): 10, (1, 2): 2, (2, 3): 2, (1, 4): 1, (3, 4): 6, (0, 2): 5, (2, 1): 3} multidict( ) 関数は，辞書を入力 キー（枝）のリスト， 費用を表す辞書 cost を返す．

モデルの構築 m=Model() x={} for (i,j) in E: x[i,j] = m.addVar(name="x(%s,%s)"%(i,j)) m.update() m.addConstr( -x[0,1] - x[0,2] == -1 , name="source") m.addConstr( x[0,1] + x[2,1] -x[1,2] -x[1,4] ==0 , name="1" ) m.addConstr( x[0,2] + x[1,2] -x[2,1] -x[2,3] ==0 , name="2") m.addConstr( x[2,3] - x[3,4] ==0 , name="3") m.addConstr( x[1,4] + x[3,4] ==1 , name="sink") m.setObjective(quicksum( cost[i,j]*x[i,j] for (i,j) in E ), GRB.MINIMIZE) m.optimize()

結果の出力 最適値 Optimal Value= 9.0 0 1 0.0 1 2 0.0 1 4 1.0 2 3 0.0 2 1 1.0 3 4 0.0 0 2 1.0 source -5.0 1 3.0 2 0.0 3 2.0 sink 4.0 print "Optimal Value=",m.ObjVal for (i,j) in x: print i,j,x[i,j].X for c in m.getConstrs(): print c.ConstrName, c.Pi 最適解 モデルオブジェクト m のgetConstrs()メソッドで制約オブジェクトのリストを得る 各制約 c に対して，ConstrNameで制約名， Pi（π）で双対変数を得る！ 最適双対解

より一般的な実装 隣接する点のリスト Out, Inの準備 from gurobipy import * E, cost = multidict( {(0,1):10, (0,2):5, (1,2):2, (1,4):1, (2,1):3, (2,3):2, (3,4):6} ) V=range(5) Out =[ [] for i in V ] In =[ [] for i in V ] for (i,j) in E: Out[i].append(j) In[j].append(i) print "Out=",Out print "In=",In 隣接する点のリスト Out, Inの準備 Out= [[1, 2], [2, 4], [3, 1], [4], []] In= [[], [0, 2], [1, 0], [2], [1, 3]]

モデルの構築 m=Model() x={} for (i,j) in E: x[i,j] = m.addVar(name="x(%s,%s)"%(i,j)) m.update() for i in V: if i==0: m.addConstr( quicksum( x[i,j] for j in Out[i]) ==1 ) elif i==4: m.addConstr( quicksum( x[j,i] for j in In[i]) ==1 ) else: m.addConstr( quicksum( x[j,i] for j in In[i]) == quicksum( x[i,j] for j in Out[i]) ) m.setObjective(quicksum( cost[i,j]*x[i,j] for (i,j) in E ), GRB.MINIMIZE)

モデルの確認 m.update() m.write("sp.lp") モデル更新 update()の後で Writeメソッド Minimize 10 x(0,1) + 2 x(1,2) + 2 x(2,3) + x(1,4) + 6 x(3,4) + 5 x(0,2) + 3 x(2,1) Subject To R0: x(0,1) + x(0,2) = 1 R1: x(0,1) - x(1,2) - x(1,4) + x(2,1) = 0 R2: x(1,2) - x(2,3) + x(0,2) - x(2,1) = 0 R3: x(2,3) - x(3,4) = 0 R4: x(1,4) + x(3,4) = 1 Bounds End m.update() m.write("sp.lp") モデル更新 update()の後で Writeメソッド ファイル “sp.lp” が 出力される