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

Presentation on theme: "最大最小性, 双対性 min-max property duality"— Presentation transcript:

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

2 … … 最大最小性 ≦ １００ １００ ５０ １０ ５００ ２５ ５ ５００ 任意のコインの大きさ 任意の貯金箱の口の大きさ C C B A
世界各国のコイン がある． 直径最大のコインを 選びたい １０ … ５００ ２５ ５ もしピッタリなら そのコインは最大 貯金箱の口は最小 ５００ 　　任意のコインの大きさ 任意の貯金箱の口の大きさ ≦ C C B A D 世界中のどの コインも入る口を 持つ貯金箱 …

3 畳パズル

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

5 畳パズル 問１ 問１　では図２のマス目のパターンではどうでしょう．何畳まで置けますか？ 図２

6 畳パズル 問２ 問２　では図３のマス目のパターンではどうでしょう．何畳まで置けますか？ 図３

7 畳パズル 問３ 問３　では図３のマス目のパターンではどうでしょう．何畳まで置けますか？ 図４

8 畳パズル 問４ 問４　では図５のマス目のパターンではどうでしょう．何畳まで置けますか？ 図５

9 畳パズル 問４の答え（？）

10 座布団パズル

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

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

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

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

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

16 座布団パズル 問４ 問４　図５のマス目のパターンでは何枚でたりますか．　 図５

17 座布団パズル 問４の答え（？）

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

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

20 このような問題例でも ４２マス

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

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

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

24 五翼放射状建物

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

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

27 畳のパッキング問題と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本の枝が同じ点で出会わない ように詰める

28 畳のカバーリング問題と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のタイルをピンクに塗り， 畳をどのようにおいてもピンクの タイルを含むようにする． 節点をピンクに塗り，どの枝もピンクの 節点に接するようにする．

29 畳の最大枚数と座布団の最小枚数が一致する例 最大マッチングサイズと最小節点カバーサイズが一致する例
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

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

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

32 線形計画問題 (Linear Programming)
目的関数 x1 + 2 x2　⇒ 最大化 制約条件 x x2　≦ 3 x1 + 3x2　≦ 6 x1 + x2　≦ 4 x1≧0, x2≧0. 双対問題D : 目的関数 3 y1 + 6 y2 + 4 y3 　⇒ 最小化 制約条件 y 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の実行可能解であり，かつ，目的関数値はともに５である のでいずれも最適解であることが分かる．

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

34 V1 V2 max |M|＝ min |C| （IPでもギャップ無し） ２部グラフの最大マッチング問題
マッチング：M⊆E, 節点カバー： C⊆V |M|≦|C| 　　　（双対性） max |M|＝ min |C| （IPでもギャップ無し）

35 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-困難）

36 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 30x x2 ≦30 x1, x2≧0 LPの最適解 x1, x2∈{0,1,2,...,40} IPの最適解 20 10 x1

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

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

39 最大フロー問題 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

40 フローの定義 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への流量８のフローが得られた　・・・　これは最大か？

41 最大最小性 【最小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

42 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

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

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

45 最大フローアルゴリズム （最大パスアルゴリズムで説明）

46 最大パスアルゴリズム 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

47 最大パスアルゴリズム 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

48 最大パスアルゴリズム 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

49 最大パスアルゴリズム 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

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

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

52 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

53 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

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

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

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

57 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

58 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

59 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

60 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

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

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

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

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

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

66 画像の二値化（近傍の考慮１） 総和 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 切り上げ ⇒　いつでも要求を満たす二値化は可能か？

67 画像の二値化問題（近傍の考慮１）

68 画像の二値化（近傍の考慮１） s 3/2 2/1 数値/数値は 上限/下限 1/0 s からt へ流量７以上の フローがあるので、 流量７か８の整数値の フローがある 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