最大最小性, 双対性 min-max property duality

Slides:



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

模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
第6回 線形計画法の解法(4) 混合最小値問題 山梨大学.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
凸関数じゃないですか (最大値/最小値を求める問題) 目的関数を固定する (最大値/最小値を最小/最大化する問題)
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
豊中高校土曜講座「数学セミナー2003」 プラトン多面体の数学 なぜ正多面体は5種類しかないのか 大阪府立豊中高等学校 深川 久.
動的計画法 表の作成 制約の追加 練習問題.
第八回  シンプレックス表の経済的解釈 山梨大学.
動的計画法 表の作成 制約の追加 練習問題.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
第三回 線形計画法の解法(1) 標準最大値問題 山梨大学.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
整数計画法を用いた スリザーリンクの解法 杉村 由花 (東京大学)
An Algorithm for Enumerating Maximal Matchings of a Graph
組合せ最適化 輪講 第1回 ERATO研究員 川原 純.
分子生物情報学 動的計画法に基づく配列比較法 (ペアワイズアライメント法)
JAG Regional Practice Contest 2012 問題C: Median Tree
土木計画学 第11回(12月21日) 土木計画と説明責任 計画における代替案の作成1 担当:榊原 弘之.
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
第5回 双対問題 テキストp 内容 双対問題の導出 式を足しあわせる方法 Lagrange緩和 相補性条件 双対辞書
第 七 回 双対問題とその解法 山梨大学.
1章前半.
Probabilistic Method 6-3,4
A path to combinatorics 第6章前半(最初-Ex6.5)
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
Selfish Routing and the Price of Anarchy 第2回
計算量理論輪講 岩間研究室 照山順一.
Yuri Y. Boykov Marie-Pierre Jolly
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
4. 組み合わせ回路の構成法 五島 正裕.
割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース(マッチング) • 3種類のものを割当てる問題.
シャノンのスイッチングゲームにおけるペアリング戦略について
第4章 組合せ論理回路 (4) Quine McCluskeyの方法.
ディジタル回路 3. 組み合わせ回路 五島 正裕 2018/11/28.
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
モデルの逆解析 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
7.4 Two General Settings D3 杉原堅也.
計算量理論 1. マトロイドと貪欲アルゴリズム 1. Matroids and the Greedy Algorithm
25. Randomized Algorithms
Selfish Routing and the Price of Anarchy 4.3
b f c a d e g h a b c d e f g 図1 図2 2012年度 有限幾何学 期末試験
計算量理論輪講 chap5-3 M1 高井唯史.
A First Course in Combinatorial Optimization Chapter
First Course in Combinatorial Optimization
連続領域におけるファジィ制約充足問題の 反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.
First Course in Combinatorial Optimization
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
SIFTとGraph Cutsを用いた 物体認識及びセグメンテーション
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
第16章 動的計画法 アルゴリズムイントロダクション.
Max Cut and the Smallest Eigenvalue 論文紹介
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
d b c e a f 年度 有限幾何学 中間試験 問1 次の用語の定義をそれぞれ述べよ.
指令1 三角形の謎にせまれ!.
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
ヒープソート.
Chapter5 Systems of Distinct Representatives
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
離散数学 11. その他のアルゴリズム 五島.
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
アルゴリズム ~すべてのプログラムの基礎~.
Presentation transcript:

最大最小性, 双対性 min-max property duality

… … 最大最小性 ≦ 100 100 50 10 500 25 5 500 任意のコインの大きさ 任意の貯金箱の口の大きさ C C B A 世界各国のコイン がある. 直径最大のコインを 選びたい 10 … 500 25 5 もしピッタリなら そのコインは最大 貯金箱の口は最小 500   任意のコインの大きさ 任意の貯金箱の口の大きさ ≦ C C B A D 世界中のどの コインも入る口を 持つ貯金箱 …

畳パズル

畳パズル 図1 半畳は1畳の半分で正方形の形をしています.図1では半畳の大きさのマス目が6個からなる床を上から見た絵です.この床に畳を何畳置くことができるでしょうか.畳同士が重なったり,マス目のないところにはみ出してはいけません. 答えの例

畳パズル 問1 問1 では図2のマス目のパターンではどうでしょう.何畳まで置けますか? 図2

畳パズル 問2 問2 では図3のマス目のパターンではどうでしょう.何畳まで置けますか? 図3

畳パズル 問3 問3 では図3のマス目のパターンではどうでしょう.何畳まで置けますか? 図4

畳パズル 問4 問4 では図5のマス目のパターンではどうでしょう.何畳まで置けますか? 図5

畳パズル 問4の答え(?)

座布団パズル

座布団パズル 座布団パズル: 図1の床には6個のマス目があります.この床の上に座布団を置きます.ただし, ★各マス目に1枚置くか,置かないかのいずれか. ★それと,座布団の置かれないマス目が隣り合ってはいけません  (隣り合うとは境界辺で接している状況です). もちろんすべてのマス目に座布団を置いてしまえば,空きのマス目がなくなるのでこれらの規則を満たします.目標は規則を満たしつつできるだけ使う座布団の枚数を少なくすることです. 図1

座布団パズル 空いているマス同士が 隣り合っているのでダメ よい置き方

座布団パズル 問1 問1 図2のマス目のパターンで座布団の置かれないマス目が隣り合わないように座布団を置いてください.何枚でたりますか. 問1 図2のマス目のパターンで座布団の置かれないマス目が隣り合わないように座布団を置いてください.何枚でたりますか.  図2

座布団パズル 問2 問2 図3のマス目のパターンで座布団の置かれないマス目が隣り合わないように座布団を置いてください.何枚でたりますか. 問2 図3のマス目のパターンで座布団の置かれないマス目が隣り合わないように座布団を置いてください.何枚でたりますか.  図3

座布団パズル 問3 問3 図4のマス目のパターンで座布団の置かれないマス目が隣り合わないように座布団を置いてください.何枚でたりますか. 問3 図4のマス目のパターンで座布団の置かれないマス目が隣り合わないように座布団を置いてください.何枚でたりますか.  図4

座布団パズル 問4 問4 図5のマス目のパターンでは何枚でたりますか.  図5

座布団パズル 問4の答え(?)

畳パズルと座布団パズル の答えの比較

畳パズルと座布団パズル の答えの比較

このような問題例でも 42マス

このような問題例でも 証拠:どうやって計算したかに関係なく 最適性が確認できる.

このような問題例でも 証拠:どうやって計算したかに関係なく 最適性が確認できる.

最小節点カバー問題 (minimum vertex cover) すべての通路(枝)を監視できるように コーナー(節点)に監視員を配置したい. 監視員の集合(節点カバー) 人件費は高い.監視員の集合(節点カバー)を最小にしたい.

五翼放射状建物

最大マッチング問題 (maximum matching) ペア(マッチング)の数を最大にしたい. 一人(節点)は高々1組のペアにしか参加できない.

1×2の矩形をいくつパッキングできるか? ここで実際にクラスタグラフを自動描画するためにはどうしたらよいのか、ということですが 以下の4つの条件を満たす描画を求める問題を考えます.

畳のパッキング問題と2部グラフのマッチング問題 a 1 2 b 2 1 a 4 c 3 3 d d 4 b 5 c 6 f e e 5 f ここで実際にクラスタグラフを自動描画するためにはどうしたらよいのか、ということですが 以下の4つの条件を満たす描画を求める問題を考えます. 6 畳が互いに重ならない ように詰める 2本の枝が同じ点で出会わない ように詰める

畳のカバーリング問題と2部グラフの節点カバー問題 a 1 2 b 2 1 a 4 c 3 3 d d 4 b 5 c 6 f e e 5 f ここで実際にクラスタグラフを自動描画するためにはどうしたらよいのか、ということですが 以下の4つの条件を満たす描画を求める問題を考えます. 6 1×1のタイルをピンクに塗り, 畳をどのようにおいてもピンクの タイルを含むようにする. 節点をピンクに塗り,どの枝もピンクの 節点に接するようにする.

畳の最大枚数と座布団の最小枚数が一致する例 最大マッチングサイズと最小節点カバーサイズが一致する例 a 1 2 b 2 1 a 4 c 3 3 d d 4 b 5 c 6 f e e 5 ここで実際にクラスタグラフを自動描画するためにはどうしたらよいのか、ということですが 以下の4つの条件を満たす描画を求める問題を考えます. f 6

e1 v3 v1 e2 max x1+x2+x3+x4 v4 e3 v2 e4 v5 x1 x2 x3 x4 2部グラフの最大マッチング問題 e1 v2 v1 v4 v3 v5 e2 e3 e4 V:点集合 E:辺集合 max x1+x2+x3+x4 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 1 E V x1 x2 x3 x4 1 ≦ ⇒ x1,x2,x3,x4≧0 (LP) 2部グラフなら 最適値が変わらない x1,x2,x3,x4∈{0,1}

双対問題 e1 v3 v1 min y1+y2+y3+y4 +y5 e2 v4 e3 v2 e4 y1 v5 y2 y3 y4 y5 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 1 E V e3 v2 y1 y2 y3 y4 y5 e4 v5 ⇒ y1,...,y5∈{0,1}(IP) ・2部グラフなら 最適値が変わらない ・どの辺も少なくとも1個は 接続する点の部分集合C⊆V (節点カバー) ≧ 1 1 1 1 y1,...,y5≧0 (LP)

線形計画問題 (Linear Programming) 目的関数 x1 + 2 x2 ⇒ 最大化 制約条件 x1 - x2 ≦ 3 x1 + 3x2 ≦ 6 x1 + x2 ≦ 4 x1≧0, x2≧0. 双対問題D : 目的関数 3 y1 + 6 y2 + 4 y3  ⇒ 最小化 制約条件 y1 + y2 + y3 ≧ 1 -y1 + 3y2  + y3 ≧ 2 y1≧0, y2≧0 , y3≧0. 双対定理: P,Dの任意の実行可能解 x=(x1, x2),y=(y1, y2 , y3) に対し常に以下が成立する.   x1 + 2 x2 ≦ 3 y1 + 6 y2 + 4 y2 . (理由: x1+2x2 ≦ (y1+y2+y3)x1 +(-y1+3y2+y3)x2 = (x1-x2)y1+(x1+3x2)y2 +(x1+x2)y2 ≦ 3y1+6y2 + 4y2 ) 特に,等号が成立する場合は,x, y はそれぞれ最適解 (Pの最大解,Dの最小解) となる. x=(x1, x2)=(3,1), y=(y1, y2 , y3)=(0,1/2,1/2) は,P, Dの実行可能解であり,かつ,目的関数値はともに5である のでいずれも最適解であることが分かる.

V1 V2 2部グラフの最大マッチング問題 V:点集合 E:辺集合 マッチング:どの点においても高々1本しか接続しない 辺の部分集合M⊆E 節点カバー:どの辺も少なくとも1個は接続する点の         部分集合C⊆V

V1 V2 max |M|= min |C| (IPでもギャップ無し) 2部グラフの最大マッチング問題 マッチング:M⊆E, 節点カバー: C⊆V |M|≦|C|    (双対性) max |M|= min |C| (IPでもギャップ無し)

max |M|< min |C| となることがある(ギャップあり) 一般グラフの最大マッチング問題 max |M|=1 min |C|=2 LP解 1/2, 1/2, 1/2 マッチング:M⊆E, 節点カバー: C⊆V |M|≦|C|    (双対性) max |M|< min |C| となることがある(ギャップあり) ⇒ NP-困難となることが多い  (最小の節点カバーを見つける問題はNP-困難)

IP=LP+整数制約 x2 max x1+ x2 s.t. 10 x1+ 20x2 ≦40 30x1+ 10 x2 ≦30 x1, x2≧0 離散最適化問題  = 線形計画問題 + 変数の整数値制約 (整数計画問題 IP)      LP x2 max x1+ x2 s.t. 10 x1+ 20x2 ≦40 30x1+ 10 x2 ≦30 x1, x2≧0 LPの最適解 x1, x2∈{0,1,2,...,40} IPの最適解 20 10 x1

問題の双対性 パッキング問題の解の最大値 ≦ カバーリング問題の解の最小値 パッキング問題の解の最大値 = カバーリング問題の解の最小値 パッキングの整数計画問題 カバーリングの整数計画問題 ≦ ≦ パッキングからの線形計画問題 カバーリングからの線形計画問題     =   最適値は一致 等号成立する場合とそうでない場合がある ここで実際にクラスタグラフを自動描画するためにはどうしたらよいのか、ということですが 以下の4つの条件を満たす描画を求める問題を考えます. パッキング問題の解の最大値 = カバーリング問題の解の最小値 特徴づけ: 等号成立する場合は最適性を示す証拠として使える

最大最小性の成立つ問題 ・2部グラフの最大マッチング問題, ・2部グラフの最小節点カバー問題 ・最大フロー問題 ・最小カット問題 ・2部グラフの最大マッチング問題,  ・2部グラフの最小節点カバー問題 ・最大フロー問題 ・最小カット問題 ・一般グラフの  最大マッチング問題 ・マトロイド LPの最適解

最大フロー問題 3 4 2 4 1 4 3 2 1 3 3 3 1 4 【最大フロー問題】 s からt への輸送量最大の 目的地t 出発地s ルートを見つけたい 枝の数値 =容量(パイプの太さ) 3 4 2 4 1 目的地t  出発地s 4 3 2 1 3 3 3 1 4

フローの定義 3 4 2 4 1 4 3 2 1 3 3 3 4 1 【最大フロー問題】 s からt への輸送量最大の ルートを見つけたい 枝の数値 =容量(パイプの太さ) 3 4 2 4 目的地t  出発地s 1 4 3 2 1 3 3 3 4 1 sからtへの流量8のフローが得られた ・・・ これは最大か?

最大最小性 【最小s,t-カット問題】 点の集合をA, Bに分ける分割のうち(s ∈A, t ∈B), AからBへ向かう枝の容量和を最小にするものを求めよ B 枝の数値 =容量(パイプの太さ) A側からB側へは 最大で10しか フローが通れない 3 4 2 4 A 1 4 2 t s 3 4 1 3 3 3 1

s t 最大最小性 B A 3 4 2 4 1 4 2 3 4 1 3 3 3 1 8 しかフローが通れない A側からB側へは最大で 考えてみよう B A sからtへの流量 8 のフローが得られた ・・・ これは最大か? Yes 3 4 2 4 1 4 2 t s 3 4 1 3 3 3 1

最大フロー問題 フローの更新方法: フローの変更を考慮した 到達可能性グラフ グラフ上のフロー s t s t s t s t

s s t t 最大フロー問題 ①最大フロー問題はO(n3)時間で解ける。 ②最大フローの大きさは、s,tを分離するカットの最小値に等しい。 ③各枝の容量(上限値)が整数ならどの枝上でも整数値の最大フローが存在する s 上限 3 下限 1 ※枝に下限値(最低流れてほしい量)がある場合の扱い t s t 上限 2 下限 0 上限 1

最大フローアルゴリズム (最大パスアルゴリズムで説明)

最大パスアルゴリズム v4 v7 v1 v9 t s v3 v6 v2 v8 v5 アルゴリズム: 次の手続きをsから到達可能な点の集合Sにtが含まれなくなるまで (つまり,sからtへのパスが取れなくなるまで)反復する. 最後に得られたグラフにおいて向きが反転している枝の集合が最大のs,t-パス集合を与える. sからtへの有向パスを見つけ,そのパス上の枝の向きを反転させる. v4 v7 v1 v9 t s v3 v6 v2 v8 v5

最大パスアルゴリズム v4 v7 v1 v9 t s v3 v6 v2 v8 v5 v4 v7 v1 v9 t s v3 v6 v2 v8 パス:s, v1, v4, v7, v3, v6, t が見つかる.このパス上の枝の向きを反転させる. v4 v7 v1 v9 t s v3 v6 v2 v8 v5

最大パスアルゴリズム v4 v7 v1 v9 t s v3 v6 v2 v8 v5 v4 v7 v1 v9 t s v3 v6 v2 v8 パス:s, v5, v6, v8, t が見つかる.このパス上の枝の向きを反転させる. v4 v7 v1 v9 t s v3 v6 v2 v8 v5

最大パスアルゴリズム v4 v7 v1 v9 t s v3 v6 v2 v8 v5 v4 v7 v1 v9 t s v3 v6 v2 v8 パス:s, v3, v7, t が見つかる.このパス上の枝の向きを反転させる. v4 v7 v1 v9 t s v3 v6 v2 v8 v5

最大パスアルゴリズム sからtへのパスは取れない.S={s, v1, v2, v3, v4, v5} v4 v7 v1 v9 t s v3

最大パスアルゴリズム 演習問題 s t v3 v4 v5 v6 v7 v1 v2

s t v3 v4 v5 v6 v7 v1 v2 s t v3 v4 v5 v6 v7 v1 v2 s t v3 v4 v5 v6 v7 v1 v2 s t v3 v4 v5 v6 v7 v1 v2

s t v3 v4 v5 v6 v7 v1 v2 s t v3 v4 v5 v6 v7 v1 v2 s t v3 v4 v5 v6 v7 v1 v2 s t v3 v4 v5 v6 v7 v1 v2

LPで見る最大フロー問題, 最小カット問題の双対性

最大フロー問題の応用 2部グラフの最大マッチング 画像の2値化

2部グラフ最大マッチングを最大パスアルゴリズムで解く u1 v1 u2 v2 u3 v3 u4 v4

2部グラフ最大マッチングを最大パスアルゴリズムで解く u1 v1 u2 v2 s t u3 v3 u4 v4 パス:s, u1, v1, t が見つかる.このパス上の枝の向きを反転させる. u1 v1 u2 v2 s t u3 v3 u4 v4

2部グラフ最大マッチングを最大パスアルゴリズムで解く u1 v1 u2 v2 s t u3 v3 u4 v4 パス:s, u2, v2, t が見つかる.このパス上の枝の向きを反転させる. s t u1 u2 u3 v1 v2 v3 u4 v4

2部グラフ最大マッチングを最大パスアルゴリズムで解く s t u1 u2 u3 v1 v2 v3 u4 v4 パス:s, u4, v3, t が見つかる.このパス上の枝の向きを反転させる. s t u1 u2 u3 v1 v2 v3 u4 v4

2部グラフ最大マッチングを最大パスアルゴリズムで解く s t u1 u2 u3 v1 v2 v3 u4 v4 sからtへのパスは取れない.S={s, u2, u3, v2} s t u1 u2 u3 v1 v2 v3 u4 v4

最大フロー問題の応用:画像の二値化問題 原画像 単純二値化

閾値による単純二値化 1 閾値 0.5 0.6 0.9 0.5 0.7 0.2 0.3 0.4

二値化画像の例 原画像 単純二値化

二値化画像の例 原画像 近傍を考慮した方法

二値化データの比較 単純二値化 近傍を考慮した方法

画像の二値化(近傍の考慮1) 総和 7.5 列和 2 1 行和 総和 7 0.6 0.9 0.5 0.7 0.2 0.3 0.4 行和 2.3 行和 2.5 行和 1.6 行和 1.1 列和 2.2 列和 1.9 列和 2.1 列和 1.3 要求: 二値化した後の行(列)和 = 元の値の切り下げ or 切り上げ ⇒ いつでも要求を満たす二値化は可能か?

画像の二値化問題(近傍の考慮1)

画像の二値化(近傍の考慮1) s 3/2 2/1 数値/数値は 上限/下限 1/0 s からt へ流量7以上の フローがあるので、 流量7か8の整数値の フローがある 0.5 0.6 0.7 0.5 t 3/2 2/1 8/7 0.9 0.7 0.7 0.2 0.5 0.3 0.4 0.4 0.3 0.3 0.3 0.2