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

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム.
人工知能 ( Artificial Intelligence ) 状態空間表現と探索 State Space Representation and Search Lecture 2 田中美栄子.
Determining Optical Flow. はじめに オプティカルフローとは画像内の明る さのパターンの動きの見かけの速さの 分布 オプティカルフローは物体の動きの よって変化するため、オプティカルフ ローより速度に関する情報を得ること ができる.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
情報システム ネットワークフロー.
コンピュータビジョン特論B - Graph Cuts - 永橋知行.
  スケジュール管理手法PERT-Time      解 説    “最早開始時間計算のアルゴリズム”
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
第八回  シンプレックス表の経済的解釈 山梨大学.
原案:西出 テスト 伊藤.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
重回帰分析入門 経済データ解析 2009年度.
    有限幾何学        第8回.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
5.チューリングマシンと計算.
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
5.チューリングマシンと計算.
An Algorithm for Enumerating Maximal Matchings of a Graph
重回帰分析入門 経済データ解析 2011年度.
組合せ最適化 輪講 第1回 ERATO研究員 川原 純.
    有限幾何学        第12回.
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
第3章 重回帰分析 ー 計量経済学 ー.
第3章 重回帰分析 ー 計量経済学 ー.
最大最小性, 双対性 min-max property duality
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
第4章 空間解析 2.ネットワーク分析 (3) ネットワーク構造分析
Selfish Routing and the Price of Anarchy 第2回
Selfish routing 川原 純.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
情報学研究科 通信情報システム専攻 小野寺研究室 M1 奥村 佳弘
MPIを用いた並列処理 ~GAによるTSPの解法~
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
算法数理工学 第8回 定兼 邦彦.
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
第3回 アルゴリズムと計算量 2019/2/24.
25. Randomized Algorithms
Selfish Routing and the Price of Anarchy 4.3
モバイルエージェントネットワークの拡張とシミュレーション
計算量理論輪講 chap5-3 M1 高井唯史.
First Course in Combinatorial Optimization
様々な情報源(4章).
第4章 空間解析 2.ネットワーク分析 (1) 最短経路検索
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
情報知能学科「アルゴリズムとデータ構造」
問題作成、解説担当:中島 副担当:坪坂、松本
Selfish Routing 4章前半 岡本 和也.
5.チューリングマシンと計算.
Max Cut and the Smallest Eigenvalue 論文紹介
Selfish Routing and the Price of Anarchy
アルゴリズムとデータ構造 2011年6月16日
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
11.動的計画法と擬多項式時間アルゴリズム.
電気回路学Ⅱ 通信工学コース 5セメ 山田 博仁.
重回帰分析入門 経済データ解析 2008年度.
4.プッシュダウンオートマトンと 文脈自由文法の等価性
重回帰分析入門 (第5章補足) 統計学 2007年度.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
離散数学 11. その他のアルゴリズム 五島.
アルゴリズムとデータ構造 2013年6月20日
MPIを用いた 並列処理 情報論理工学研究室 06‐1‐037‐0246 杉所 拓也.
各種荷重を受ける 中空押出形成材の構造最適化
アルゴリズム ~すべてのプログラムの基礎~.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

第4章 空間解析 2.ネットワーク分析 (2) 最大流問題 第4章 空間解析 2.ネットワーク分析 (2) 最大流問題 久保田光一 kubota@ise.chuo-u.ac.jp

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

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

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

ネットワークの枝の容量 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) を流れる量は0以上容量c(u,v) 以下の値でなければならない. 新宿 u 1 出口 t :東京

ネットワーク上のフロー 1 1 1 1 1 1 フロー f の値 F は 3 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 :東京

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

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

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

残余ネットワーク 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 を表現するための残余ネットワークを構成する. ・これは,枝を流れる量を x, 容量を yとするとき,その枝だけに着目すると,あと y-x だけ流量を増やせることを,重みがy-xの順方向の有向枝で表現する. ・流量をxだけ減らせるということを,逆方向の流量をxだけ増やせるという意味で,重みがxの逆方向の有向枝で表現する. x 元のネットワーク 残余ネットワーク あとどれだけ流せるか

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

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

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

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

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

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

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

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

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

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