第4章 空間解析 2.ネットワーク分析 (2) 最大流問題

Presentation on theme: "第4章 空間解析 2.ネットワーク分析 (2) 最大流問題"— Presentation transcript:

1 第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
第4章　空間解析 2.ネットワーク分析 (2) 最大流問題 久保田光一

2 最大流 通信量最大化 １ ←回線容量 出発地：池袋 ３ ３ 御茶ノ水 ３ ３ 秋葉原 新宿 ４ １ 目的地：東京 １
最大流　通信量最大化 １ ←回線容量 出発地：池袋 ３ ３ 御茶ノ水 ３ ３ 秋葉原 新宿 ４ １ ・例として挙げた鉄道網に沿って，図のような回線を引き，その回線の通信容量を設定したとする． ・通信容量の単位は単位時間あたり送ることができるデータとする． ・このとき，池袋から東京まで単位時間あたり最大で何単位のデータが送れるのかを知りたい． ・このような問題を解くために利用するモデルが，ネットワークフローであり，ネットワークフローに関する最大流問題である． 目的地：東京 １

3 ネットワークフロー 水などの配管や道路の交通量や輸送量などを表現するための「ネットワーク」を考える．
ネットワークの構造は，地点を頂点，配管や道路を枝とするようなグラフ G=(V,E) で表される. ここでは，Gは単純なグラフとする（後述）． 始点 s (source) と終点 t (sink) を定めて，ネットワークの枝に水や物などを流すとき，それをフロー f という．水流，物流，交通流など． フローfの値 F とは，始点 s から流れ出る総量であり，終点に流れ込む総量（途中で流量は保存）でもある．

4 フローの制約と最大流問題 各枝(u,v) には容量（capacity）を表す非負の実数 c(u,v) が与えられ，枝(u,v)のフロー f(u,v) は 次の制約を満たす： 最大流問題は様々なフロー f の中で，fの値 F の最大値とそのときのフロー f を求める問題． ・ここで，総和記号は，s または vに入ってくる枝の始点全体，あるいは，ｔ または v から出ていく枝の終点全体に関する和を表す．

5 ネットワークの枝の容量 1 3 3 3 3 4 1 1 c(s,u)= 各枝には流れる量の最大値（これを「容量」という）が与えられている
秋葉原 w 枝（s,u）の容量を c(s,u) と記す 3 御茶ノ水 v 3 c(s,u)= 3 3 4 1 ・流れを考えるので，流れの方向を定めて，有向グラフ・ネットワークで考える． ・ここでは流れの入口 s （source)を池袋，出口 t （sink)を東京とする． ・池袋から東京に，データを送信することを考える．ただし，ここでは，データは水のような液体として 　考えることができるように，データの送信単位は十分小さく，　データの送信順序は問わないとする． ・各枝(u,v) には，その枝を流れるフロー f(u,v) 量の最大値として「容量c(u,v)」が与えられている． ・各枝(u,v) を流れる量は０以上容量c(u,v) 以下の値でなければならない． 新宿 u 1 出口 t ：東京

6 ネットワーク上のフロー 1 1 1 1 1 1 フロー f の値 F は ３ f(s,u)= 各枝には流れる量は「容量」以下
秋葉原 w 枝（s,u）を流れる量 を f(s,u) と記す 1 御茶ノ水 v 1 f(s,u)= 1 1 ・フローそれ自体は様々なものがありうる．その一つの例． ・各枝の数値はその枝(u,v) を流れるフローのその枝での流量f(u,v)を表す． ・フロー f の値 F は，入口から流れ出る流量の総和であり，出口から流れ出る流量の総和． ・途中の頂点では，流れ込む量の総和と，流れ出る量の総和は等しい 新宿 u 1 出口 t ：東京

7 枝の流量 / 容量 の記載法 1/1 1/3 1/3 0/3 1/4 0/3 1/1 1/1 x/y ： 流量 ｘ が容量 ｙ の枝に存在
枝の流量　/　容量　の記載法 入口：池袋 1/1 秋葉原 1/3 1/3 御茶ノ水 0/3 1/4 0/3 1/1 ・枝を流れるフローと，その枝の容量を合わせて整理して記述すると，このようになる． 新宿 1/1 x/y ： 流量 ｘ が容量 ｙ の枝に存在 出口：東京

8 フォード・ファルカーソン法 Ford・Fulkerson法は基本的な考え方． まず，容量の制限を満たすフロー f を与える．
増加可能経路 ｐ が存在するなら， フロー f を p に沿って増加させる． 存在しなければ終了 ・Ford　Fulkerson法は基本となる考え方である．ここに出てくる増加可能経路ｐの見つけ出し方にいろいろな方法があり，各種アルゴリズムとして提案されている． ・基本的な考え方は，初期フローを選ぶ． ・現在のフローについて，流量を増やせるかどうかを，増加可能経路ｐの有無で判断する．

9 増加可能経路 1/1 1/3 1/3 0/3 1/4 0/3 1/1 1/1 x/y ： 流量 ｘ が容量 ｙ の枝に存在 池袋 秋葉原
御茶ノ水 0/3 1/4 0/3 1/1 ・この図で赤で示した経路は，増加可能経路のひとつである． ・実際，この経路上の枝のフローを全て１だけ増やしても，制約に違反せずフローを構成できる． 新宿 1/1 x/y ： 流量 ｘ が容量 ｙ の枝に存在 東京

10 残余ネットワーク y - x x / y x 元のネットワーク 残余ネットワーク
各枝(u,v)には流量 x=f(u,v) と容量 y=c(u,v) が指定される 元のネットワークの枝1本に対応し，有向枝2本を対応させ，あとどれだけ流せるかを表す残余ネットワークを構成する y - x x / y u v u v ・増加可能経路を系統立てて見出すために，与えられたフロー f を表現するための残余ネットワークを構成する． ・これは，枝を流れる量を　ｘ，　容量を　ｙとするとき，その枝だけに着目すると，あと　y-x だけ流量を増やせることを，重みがｙ－ｘの順方向の有向枝で表現する． ・流量をｘだけ減らせるということを，逆方向の流量をｘだけ増やせるという意味で，重みがｘの逆方向の有向枝で表現する． x 元のネットワーク 残余ネットワーク あとどれだけ流せるか

11 残余ネットワーク 1 1 2 3 1 2 3 1 3 1 1 入口：池袋 秋葉原 御茶ノ水 新宿 出口：東京
・各枝に具体的にフローを定めると容量制限を満たしつつさらに流すことのできる量，および，既に流している量を減らすことにより，見かけ上逆方向の流れの量を増やすことができる． ・各枝の値は，現在のフローに対して，その方向に増やすことができる流れの量の上限を表す． ・重みが０となる枝は削除して考える．図では点線で示してある． 新宿 1 出口：東京

12 増加可能経路 1 1 2 3 1 2 3 1 3 1 1 入口：池袋 秋葉原 御茶ノ水 新宿 出口：東京
・増加可能経路とは，残余ネットワーク中で，入口から出口に至る有向道（パス）のこと． ・複数存在しうるが，ここでは，図の赤で表された有向道を考える． ・増加可能経路を構成する枝に与えられている数値は，その枝に流すことができる量を表すので，各枝についてその数値の最小値を求めると， 　その増加可能経路にそって，増やすことのできる流量になる． ・ここでは，赤の有向道の枝の数値は，２，３，３，３　という4個であるので，その最小値は２になる． ・つまり，この赤の有向道に沿って，入口から流量を２だけ増やすことができることがわかる． 新宿 1 出口：東京

13 増加可能経路に沿って流量増加 1/1 1/3 3/3 2/3 3/4 2/3 1/1 1/1 x/y ： 流量 ｘ が容量 ｙ の枝に存在
池袋 1/1 秋葉原 1/3 3/3 御茶ノ水 2/3 3/4 2/3 1/1 ・増加可能経路の枝の最小値が２であったので，赤い枝の流量をそれぞれ２ずつ増やした場合の図を示す． ・赤い枝が増加可能経路を表す． 新宿 1/1 x/y ： 流量 ｘ が容量 ｙ の枝に存在 東京

14 更新した流量に関する 残余ネットワーク 1 1 1 3 2 1 2 3 2 1 1 1 入口：池袋 秋葉原 御茶ノ水 新宿 出口：東京
御茶ノ水 1 3 2 1 2 3 2 1 1 ・修正したフローについて，同様にして，再度，残余ネットワークを構成する． ・さきほどの増加可能経路に沿って，残余ネットワークを修正すればよい． 新宿 1 出口：東京

15 増加可能経路 1 1 1 3 2 1 2 3 2 1 1 1 入口：池袋 秋葉原 御茶ノ水 新宿 出口：東京
御茶ノ水 1 3 2 1 2 3 2 1 1 ・再構成された残余ネットワークで再度，増加可能経路を求める． ・ここで見出した増加可能経路の枝に付された数値は，２，１，１なので，その最小値は１である． ・したがって，この増加可能経路に沿って，流量を１だけ増やすことができる． 新宿 1 出口：東京

16 増加可能経路に沿って流量増加 1/1 2/3 3/3 3/3 4/4 2/3 1/1 1/1 x/y ： 流量 ｘ が容量 ｙ の枝に存在
池袋 1/1 秋葉原 2/3 3/3 御茶ノ水 3/3 4/4 2/3 1/1 ・増加可能経路の枝の最小値で示される流量を追加した場合の図 ・赤い枝が増加可能経路を表す． 新宿 1/1 x/y ： 流量 ｘ が容量 ｙ の枝に存在 東京

17 更新した流量に関する 残余ネットワーク 1 2 3 1 1 3 4 2 1 1 入口：池袋 秋葉原 御茶ノ水 新宿 出口：東京
御茶ノ水 3 1 1 3 4 2 1 ・同様に，残余ネットワークを構成する． ・このグラフ上では，入口から出口に到達する道が無いので，増加可能経路が存在しないことがわかる． ・この状態で，最大流を得たことになる． 新宿 1 出口：東京

18 増加可能経路が無い→終了 1 2 3 1 1 3 4 2 1 1 入口：池袋 秋葉原 御茶ノ水 新宿 出口：東京
御茶ノ水 3 1 1 3 4 2 1 ・なぜなら，出口から出る有向枝はあっても，出口に入る有向枝が無いことからすぐにわかる． 新宿 1 出口：東京

19 最大流のアルゴリズム 増加可能経路の見つけ方によって，多くのアルゴリズムが知られている．
ディニッツ（Dinic）のアルゴリズムは，幅優先探索により，増加可能経路を見出すもの． ・増加可能経路の見つけ方は，有向グラフの探索に他ならない． ・探索方法にいくつかやり方があるが，いわゆる幅優先探索を用いるディニッツのアルゴリズムが有名．

20 最大流の性質 カット： カットを構成する枝の容量の和を「カット容量」という 「最大流の値＝カット容量の最小値」が成立
ネットワーク上の頂点を二つの集合に分ける このとき，入口と出口は別々の集合に含まれるように分ける 両端点がその二つの集合に一つずつ存在するような枝の集合を「カット」という カットを構成する枝の容量の和を「カット容量」という 「最大流の値＝カット容量の最小値」が成立