第4章空間解析 2.ネットワーク分析 (2) 最大流問題久保田光一 [email protected] 地理情報科学教育用スライド ©久保田光一最大流通信量最大化１ ←回線容量出発地：池袋３３御茶ノ水３新宿１１地理情報科学教育用スライド ©久保田光一３４秋葉原目的地：東京ネットワークフロー • 水などの配管や道路の交通量や輸送量などを表現するための「ネットワーク」を考える． • ネットワークの構造は，地点を頂点，配管や道路を枝とするようなグラフ G=(V,E) で表される. ここでは，Gは単純なグラフとする（後述）． • 始点 s (source) と終点 t (sink) を定めて，ネットワークの枝に水や物などを流すとき，それをフロー f という．水流，物流，交通流など． • フローfの値 F とは，始点 s から流れ出る総量であり，終点に流れ込む総量（途中で流量は保存）でもある．地理情報科学教育用スライド ©久保田光一フローの制約と最大流問題 • 各枝(u,v) には容量（capacity）を表す非負の実数 c(u,v) が与えられ，枝(u,v)のフロー f(u,v) は次の制約を満たす： 0  f (u, v)  c(u, v),  f (s, w)  F ,  f (u, t )  F , w u  f (u, v)   f (v, w)  0. u w • 最大流問題は様々なフロー f の中で，fの値 F の最大値とそのときのフロー f を求める問題．地理情報科学教育用スライド ©久保田光一ネットワークの枝の容量各枝には流れる量の最大値（これを「容量」という）が与えられている入口 s ：池袋 1 枝（s,u）の容量を c(s,u) と記す c(s,u)= 3 3 御茶ノ水 v 3 3 新宿 u 秋葉原 w 1 4 1 出口 t ：東京地理情報科学教育用スライド ©久保田光一ネットワーク上のフロー各枝には流れる量は「容量」以下フロー f の値 F は３入口 s ：池袋 1 枝（s,u）を流れる量を f(s,u) と記す f(s,u)= 1 1 御茶ノ水 v 0 0 新宿 u 秋葉原 w 1 1 1 出口 t ：東京地理情報科学教育用スライド ©久保田光一枝の流量 / 容量の記載法入口：池袋 1/1 1/3 1/3 秋葉原御茶ノ水 0/3 0/3 新宿 1/1 1/4 1/1 x/y ：流量ｘが容量ｙの枝に存在地理情報科学教育用スライド ©久保田光一出口：東京フォード・ファルカーソン法 • Ford・Fulkerson法は基本的な考え方． • まず，容量の制限を満たすフロー f を与える． – 最初は流量が０のフロー f を考えればよい． • 現在のフロー f に対して次を繰り返す – 増加可能経路ｐが存在するなら， • フロー f を p に沿って増加させる． – 存在しなければ終了地理情報科学教育用スライド ©久保田光一増加可能経路池袋 1/1 1/3 1/3 秋葉原御茶ノ水 0/3 0/3 新宿 1/1 1/4 1/1 x/y ：流量ｘが容量ｙの枝に存在地理情報科学教育用スライド ©久保田光一東京残余ネットワーク • 各枝(u,v)には流量 x=f(u,v) と容量 y=c(u,v) が指定される • 元のネットワークの枝1本に対応し，有向枝2本を対応させ，あとどれだけ流せるかを表す残余ネットワークを構成する u x/y v u y-x v x 元のネットワーク残余ネットワークあとどれだけ流せるか地理情報科学教育用スライド ©久保田光一残余ネットワーク入口：池袋 1 秋葉原 1 1 2 3 御茶ノ水 2 3 1 1 3 新宿 1 出口：東京地理情報科学教育用スライド ©久保田光一増加可能経路入口：池袋 1 秋葉原 1 1 2 3 御茶ノ水 2 3 1 1 3 新宿 1 出口：東京地理情報科学教育用スライド ©久保田光一増加可能経路に沿って流量増加池袋 1/1 3/3 1/3 秋葉原御茶ノ水 2/3 2/3 新宿 1/1 3/4 1/1 x/y ：流量ｘが容量ｙの枝に存在地理情報科学教育用スライド ©久保田光一東京更新した流量に関する残余ネットワーク入口：池袋 1 秋葉原 3 1 0 1 御茶ノ水 2 1 2 3 2 1 1 新宿 1 出口：東京地理情報科学教育用スライド ©久保田光一増加可能経路入口：池袋 1 秋葉原 3 1 0 1 御茶ノ水 2 1 2 3 2 1 1 新宿 1 出口：東京地理情報科学教育用スライド ©久保田光一増加可能経路に沿って流量増加池袋 1/1 3/3 2/3 秋葉原御茶ノ水 3/3 2/3 新宿 1/1 4/4 1/1 x/y ：流量ｘが容量ｙの枝に存在地理情報科学教育用スライド ©久保田光一東京更新した流量に関する残余ネットワーク入口：池袋 1 秋葉原 3 2 0 1 御茶ノ水 1 0 3 4 2 1 0 新宿 1 出口：東京地理情報科学教育用スライド ©久保田光一増加可能経路が無い→終了入口：池袋 1 秋葉原 3 2 0 1 御茶ノ水 1 0 3 4 2 1 0 新宿 1 出口：東京地理情報科学教育用スライド ©久保田光一最大流のアルゴリズム • 増加可能経路の見つけ方によって，多くのアルゴリズムが知られている． • ディニッツ（Dinic）のアルゴリズムは，幅優先探索により，増加可能経路を見出すもの．地理情報科学教育用スライド ©久保田光一最大流の性質 • カット： – ネットワーク上の頂点を二つの集合に分ける • このとき，入口と出口は別々の集合に含まれるように分ける – 両端点がその二つの集合に一つずつ存在するような枝の集合を「カット」という • カットを構成する枝の容量の和を「カット容量」という • 「最大流の値＝カット容量の最小値」が成立地理情報科学教育用スライド ©久保田光一