ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94

Presentation on theme: "ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94"— Presentation transcript:

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

2 大名の最大流問題 飛脚が運べる量 （容量） 終点 始点 富士山から江戸までなるべくたくさんの氷を送りたい どのように運ぶ？ 2

3 最大流問題（グラフ理論的定義） 点集合 V 枝集合 E 有向グラフ G=(V,E) 枝の容量 u: E → R+
目的： 始点sから終点tまでの最大フロー 3

4 フローとは？ 以下の条件を満たす実数値関数x:E → R フロー整合条件 （江戸以外では氷は消費されない） 容量制約と非負制約
（飛脚の運べる量には限界がある） 4

5 Ford-Fulkerson法（アイディア）
最初は適当なフロー（例えば何も流さない）からスタート 少しずつフローを増やしていく そのためには．．． 補助ネットワークを用いる 5

6 補助ネットワーク s 1 s 1 5流せるところを 1流している状態 1／5 元の問題のネットワーク 残余容量1 1からsへあと1流せる
4 残余容量4 sから1へあと4流せる 6

7 補助ネットワーク s 1 s 1 5流せるところを 5流している状態 5／5 元の問題のネットワーク 5 補助ネットワーク 残余容量0
もう流せない 5流せる 7

8 補助ネットワーク s 1 s 1 5流せるところを 流していない状態 0／5 元の問題のネットワーク 補助ネットワーク 5 残余容量5
あと5流せる もう流せない 8

9 練習 （補助ネットワークの作り方） 1/5 0/3 2/4 2 t s 1 t 2 s 1 9

10 増加可能パス t 2 s 1 増加可能パス＝ 補助ネットワークにおいて始点sから終点tまでのパス
増加可能パスがある限り，パス内の枝の残余容量の もっとも小さい値だけフローを増やせる 1 2 t 2 s 1 4 3 2 2 (= min {4,3,2})だけ増やせる！ 10

11 Ford-Fulkerson法（アイディア）
最初は適当なフロー（例えば何も流さない）からスタート 少しずつフローを増やしていく （補助ネットワーク上で増加可能パスを見つけて，パス内の枝の残余容量の最小値だけ，パス上のフローを増やす） 増加可能パスが見つからなくなったら終わり やってみよう 11

12 Ford-Fulkerson法 1 t s 2 3 1 t s 2 3 何も流れていない 0／8 0／5 0／2 0／6 8 0／8 0／5
増加可能パス 容量5 12

13 Ford-Fulkerson法 1 t s 2 3 1 t s 2 3 流れが増えた 0／8 0／5 補助ネットワーク が変化した 0／2
5／6 8 2 3 5／8 1 t 5／5 5 増加可能パス 容量5 s 2 1 5 3 2 3 5 5 13

14 Ford-Fulkerson法 1 t s 2 3 1 t s 2 3 増加可能パス 容量2 5／8 5／5 0／2 5／6 3 5／8
14

15 Ford-Fulkerson法 1 t s 2 3 1 t s 2 3 7／8 5／5 2／2 5／6 1 7／8 5／5 5 7
増加可能パス が見つからないので 終了 s 2 1 5 1 2 3 7 5 15

16 Ford-Fulkerson法（擬似コード）
xe:=0, while 増加可能パスがある do 適当な増加可能パスPを選択 Δ:=パスP内の枝の残余容量の最小値 パスP上にフローをΔだけ増加 16

17 練習 1 2 t 1 t s s 2 0／8 0／10 0／1 0／6 枝の本数の少ないパスを使うと 回で終了
枝の本数の少ないパスを使うと　回で終了 枝の本数の多いパスを使うと　回で終了 17

18 最小カット 最大で12の氷を運べることはわかった 「12よりたくさんの氷は運べない」という にはどうしたらよいだろうか？
カットの概念を導入する 18

19 カットとは？ 点を2つのグループに分ける 始点を含むグループ 終点を含むグループ 始点を含むグループから終点を含むグループへ
向かっている有向枝の集合をカットとよぶ カットに含まれる枝の容量の合計を カットの容量とよぶ 例題のカットをみてみよう 19

20 例題のカット カット 容量は13 1 t 8 5 s 2 6 8 5 2 3 始点を含むグループ 20

21 例題のカット カット 容量は12 1 t 8 5 s 2 6 8 5 2 3 始点を含むグループ 21

22 例題のカット 始点を含むグループ 1 t 8 5 s 2 6 8 5 2 3 カット 容量は16 22

23 例題のカット 1 t 8 5 カット 容量は13 s 2 6 8 5 2 3 始点を含むグループ 23

24 例題のカット 1 t 8 5 カット 容量は13 s 2 6 8 5 2 3 始点を含むグループ 24

25 例題のカット カット 容量は14 1 t 8 5 s 2 6 8 5 2 3 始点を含むグループ 25

26 カットの性質 観察してわかったと思うが，始点から終点へは （どんなにがんばっても） カット容量よりたくさんは流すことはできない．
カット容量は始点から終点へのフローの上界を 与える！ 26

27 最小カット問題 カットの定義 最小カット問題 全てのカットに対して，容量が最小のカットを 求める問題．
実は最小カット問題は最大流問題の双対問題である． 確かめてみよう． 27

28 最大流問題の双対問題 最大流問題（主問題） 最大化問題なので，（最適）目的関数値が より大きくなるように条件を緩和する 28

29 最大流問題の双対問題 最大流問題の緩和問題 ここは0以上 ここは0 条件を緩和する 29

30 最大流問題の双対問題 最大流問題のLagrange緩和問題 目的関数をxについてまとめる 30

31 最大流問題の双対問題 最大流問題のLagrange緩和問題 目的関数を変数 x についてまとめる 31

32 最大流問題の双対問題 最大流問題のLagrange緩和問題 この問題の最適値は元の問題の最適値以上
目的関数の中で x に関係ない項を最小化し 目的関数の中で x の係数になっている項が0以下 の問題を作る 32

33 最大流問題の双対問題 最大流問題の双対問題 この問題を観察してみる zは枝に対応する変数である yは点に対応する変数である 33

34 最大流問題の双対問題 最大流問題の双対問題 枝 vw がカットに含まれるとき zvw=1， そうでないとき zvw=0
点 v が始点と同じグループに含まれるとき yv=1， そうでないとき yv=0 この問題は，最小カット問題！ 34

35 最大フロー最小カット定理 1 t s 2 3 以上より，どうやっても富士山から江戸へは 12しか氷を運べないことがいえた．
最大フローが存在するとき，最大フロー量と最小カット 容量は一致する． 1 1 t 5 7 s 2 1 5 1 2 3 7 5 始点から補助ネットワーク上で到達可能な点集合->カット 35

36 演習問題１ s t 1 3 3 4 2 2 3 3 1 最大流をFord-Fulkerson法で見つけてください．
最小カットを示してください． 36

37 演習問題２ s t 12 20 16 9 4 10 7 13 4 14 最大流をFord-Fulkerson法で見つけてください．
最小カットを示してください． 37

38 演習問題３（オプション） ここには 好きな数字を入れること 工場から市場へなるべくたくさんの物を流したい
18 4 2 7 5 12 7 市場 3 7 9 22 13 12 24 16 ここには 好きな数字を入れること 8 24 2 工場 6 4 市場 工場から市場へなるべくたくさんの物を流したい どう流したらよいだろうか？（ヒント：ダミーを使う） 38