最大最小性, 双対性
min-max property
duality
最大最小性
世界各国のコイン
がある．
直径最大のコインを
選びたい
１００
１０
１００
５０
２５
５００
５
…
もしピッタリなら
そのコインは最大
貯金箱の口は最小
５００
任意のコインの大きさ
≦
任意の貯金箱の口の大きさ
C
世界中のどの
コインも入る口を
持つ貯金箱
A
B
C
D
…
畳パズル
畳パズル
図１
半畳は１畳の半分で正方形の形をしています．図１では半畳の大きさのマ
ス目が６個からなる床を上から見た絵です．この床に畳を何畳置くことがで
きるでしょうか．畳同士が重なったり，マス目のないところにはみ出してはい
けません．
答えの例
畳パズル 問１
問１ では図２のマス目のパターンではどうでしょう．何畳まで置けますか？
図２
畳パズル 問２
問２ では図３のマス目のパターンではどうでしょう．何畳まで置けますか？
図３
畳パズル 問３
問３ では図３のマス目のパターンではどうでしょう．何畳まで置けますか？
図４
畳パズル 問４
問４ では図５のマス目のパターンではどうでしょう．何畳まで置けますか？
図５
畳パズル 問４の答え（？）
座布団パズル
座布団パズル
座布団パズル： 図１の床には６個のマス目があります．この床の上に座布団を置き
ます．ただし，
★各マス目に１枚置くか，置かないかのいずれか．
★それと，座布団の置かれないマス目が隣り合ってはいけません
（隣り合うとは境界辺で接している状況です）．
もちろんすべてのマス目に座布団を置いてしまえば，空きのマス目がなくなるのでこ
れらの規則を満たします．目標は規則を満たしつつできるだけ使う座布団の枚数を
少なくすることです．
図１
座布団パズル
よい置き方
空いているマス同士が
隣り合っているのでダメ
座布団パズル 問１
問１ 図２のマス目のパターンで座布団の置かれないマス目が隣り合わないように
座布団を置いてください．何枚でたりますか．
図２
座布団パズル 問２
問２ 図３のマス目のパターンで座布団の置かれないマス目が隣り合わないように
座布団を置いてください．何枚でたりますか．
図３
座布団パズル 問３
問３ 図４のマス目のパターンで座布団の置かれないマス目が隣り合わないように
座布団を置いてください．何枚でたりますか．
図４
座布団パズル 問４
問４ 図５のマス目のパターンでは何枚でたりますか．
図５
座布団パズル 問４の答え（？）
畳パズルと座布団パズル の答えの比較
畳パズルと座布団パズル の答えの比較
このような問題例でも
４２マス
このような問題例でも
証拠：どうやって計算したかに関係なく
最適性が確認できる．
このような問題例でも
証拠：どうやって計算したかに関係なく
最適性が確認できる．
最小節点カバー問題 (minimum vertex cover)
すべての通路（枝）を監視できるように
コーナー（節点）に監視員を配置したい．
監視員の集合（節点カバー）
人件費は高い．監視員の集合（節点カバー）を最小にしたい．
五翼放射状建物
最大マッチング問題 (maximum matching)
ペア（マッチング）の数を最大にしたい．
一人（節点）は高々１組のペアにしか参加できない．
1×2の矩形をいくつパッキングできるか？
畳のパッキング問題と2部グラフのマッチング問題
1
2
1
a
2
4
3
d
3
a
b
c
d
4
b
5
c
6
e
f
e
5
f
6
畳が互いに重ならない
ように詰める
2本の枝が同じ点で出会わない
ように詰める
畳のカバーリング問題と2部グラフの節点カバー問題
1
2
1
a
2
4
3
d
3
a
b
c
d
4
b
5
c
6
e
f
e
5
f
6
1×1のタイルをピンクに塗り，
畳をどのようにおいてもピンクの
タイルを含むようにする．
節点をピンクに塗り，どの枝もピンクの
節点に接するようにする．
畳の最大枚数と座布団の最小枚数が一致する例
最大マッチングサイズと最小節点カバーサイズが一致する例
1
2
1
a
2
4
3
d
3
a
b
c
d
4
b
5
c
6
e
f
e
5
6
f
２部グラフの最大マッチング問題
V：点集合 E:辺集合
max x1+x2+x3+x4
E
x1 x2 x3 x4
1
0
V 1
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
1
≦ 1
1
1
x1,x2,x3,x4∈{0,1}
v1
v2
e1
e2
e4
v3
e3
v4
v5
２部グラフなら
最適値が変わらない
⇒ x1,x2,x3,x4≧0 (LP)
双対問題
min y1+y2+y3+y4 +y5
E
V
1
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
≧
y1
y2
y3
y4
y5
v1
v2
e1
v3
e2
v4
e3
e4
・２部グラフなら
最適値が変わらない
・どの辺も少なくとも１個は
接続する点の部分集合C⊆V
（節点カバー）
1 1 1 1
y1,...,y5≧0 (LP)
⇒ y1,...,y5∈{0,1}(IP)
v5
線形計画問題 (Linear Programming)
主問題P :
目的関数
化
制約条件
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の実行可能解であり，かつ，目的関数値はともに５である
のでいずれも最適解であることが分かる．
２部グラフの最大マッチング問題
V:点集合
E:辺集合
V1
V2
マッチング：どの点においても高々１本しか接続しない
辺の部分集合M⊆E
節点カバー：どの辺も少なくとも１個は接続する点の
部分集合C⊆V
２部グラフの最大マッチング問題
V1
V2
マッチング：M⊆E, 節点カバー： C⊆V
|M|≦|C|
（双対性）
max |M|＝ min |C| （IPでもギャップ無し）
一般グラフの最大マッチング問題
max |M|=1
LP解 1/2, 1/2, 1/2
min |C|=2
マッチング：M⊆E, 節点カバー： C⊆V
|M|≦|C|
（双対性）
max |M|＜ min |C| となることがある（ギャップあり）
⇒ NP-困難となることが多い
（最小の節点カバーを見つける問題はNP-困難）
IP=LP+整数制約
離散最適化問題 ＝ 線形計画問題 ＋ 変数の整数値制約
（整数計画問題 IP）
LP
max x1+ x2
s.t.
10 x1+ 20x2 ≦40
30x1+ 10 x2 ≦30
x1, x2≧0
x1, x2∈{0,1,2,...,40}
x2
LPの最適解
20
IPの最適解
10
x1
問題の双対性
パッキング問題の解の最大値 ≦ カバーリング問題の解の最小値
パッキングの整数計画問題
カバーリングの整数計画問題
≦
≦
パッキングからの線形計画問題
＝
カバーリングからの線形計画問題
最適値は一致
等号成立する場合とそうでない場合がある
パッキング問題の解の最大値 ＝ カバーリング問題の解の最小値
特徴づけ: 等号成立する場合は最適性を示す証拠として使える
最大最小性の成立つ問題
・２部グラフの最大マッチング問題,
・２部グラフの最小節点カバー問題
・最大フロー問題
・最小カット問題
・一般グラフの
最大マッチング問題
・マトロイド
LPの最適解
最大フロー問題
【最大フロー問題】
s からt への輸送量最大の
枝の数値
＝容量（パイプの太さ）
ルートを見つけたい
3
出発地s
4
2
4
2
3
1
3
3
4
4 目的地t
1
1
3
フローの定義
【最大フロー問題】
s からt への輸送量最大の
ルートを見つけたい
枝の数値
＝容量（パイプの太さ）
3
4
2
出発地s
1
4
3
2
3
4
4
1
1
3
sからtへの流量８のフローが得られた ・・・ これは最大か？
3
目的地t
最大最小性
【最小s,t-カット問題】 点の集合をA, Bに分ける分割のうち（s ∈A, t ∈B），
AからBへ向かう枝の容量和を最小にするものを求めよ
B
A側からB側へは
最大で10しか
フローが通れない
A
s
4
枝の数値
＝容量（パイプの太さ）
3
2
4
1
4
2
t
3
4
3
1
1
3
3
最大最小性
A側からB側へは最大で
今度は別のA,Bの分け方を
8考えてみよう
しかフローが通れない
B
A
3
4
2
1
4
s
4
2
t
3
4
3
1
1
3
3
sからtへの流量 8 のフローが得られた ・・・ これは最大か？ Yes
最大フロー問題
フローの更新方法：
グラフ上のフロー
フローの変更を考慮した
到達可能性グラフ
s
t
s
t
s
t
s
t
最大フロー問題
①最大フロー問題はO(n3)時間で解ける。
②最大フローの大きさは、s,tを分離するカットの最小値に等しい。
③各枝の容量（上限値）が整数ならどの枝上でも整数値の最大フローが存在する
※枝に下限値（最低流れてほしい量）がある場合の扱い
上限 1
下限 0
上限 3
下限 1
s
t
s
上限 1
下限 0
上限 2
下限 0
t
最大フローアルゴリズム
（最大パスアルゴリズムで説明）
最大パスアルゴリズム
アルゴリズム： 次の手続きをsから到達可能な点の集合Sにtが含まれなくなるま
で （つまり，sからtへのパスが取れなくなるまで）反復する．
sからtへの有向パスを見つけ，そのパス上の枝の向きを反転させる．
最後に得られたグラフにおいて向きが反転している枝の集合が最大のs,t-パス集
合を与える．
v4
v1
s
v7
v9
v3
v6
v2
v5
v8
t
最大パスアルゴリズム
v4
v1
s
v7
v9
v3
t
v6
v2
v8
v5
パス：s, v1, v4, v7, v3, v6, t が見つかる．このパス上の枝の向きを反転させる．
v4
v1
s
v7
v9
v3
v6
v2
v5
v8
t
最大パスアルゴリズム
v4
v1
s
v7
v9
v3
t
v6
v2
v8
v5
パス：s, v5, v6, v8, t が見つかる．このパス上の枝の向きを反転させる．
v4
v1
s
v7
v9
v3
v6
v2
v5
v8
t
最大パスアルゴリズム
v4
v1
s
v7
v9
v3
t
v6
v2
v8
v5
パス：s, v3, v7, t が見つかる．このパス上の枝の向きを反転させる．
v4
v1
s
v7
v9
v3
v6
v2
v5
v8
t
最大パスアルゴリズム
v4
v1
s
v7
v9
v3
t
v6
v2
v8
v5
sからtへのパスは取れない．S={s, v1, v2, v3, v4, v5}
v4
v1
s
v7
v9
v3
v6
v2
v5
v8
t
最大パスアルゴリズム 演習問題
v1
v2
v3
v4
t
s
v6
v5
v7
v1
v2
v1
v2
v3
v4
v3
v4
t
s
t
s
v6
v6
v7
v5
v7
v5
v1
v2
v1
v2
v3
v4
v3
v4
t
s
t
s
v6
v6
v5
v7
v5
v7
v1
v2
v1
v2
v3
v4
v3
v4
t
s
t
s
v6
v6
v7
v5
v7
v5
v1
v2
v1
v2
v3
v4
v3
v4
t
s
t
s
v6
v6
v5
v7
v5
v7
LPで見る最大フロー問題，
最小カット問題の双対性
最大フロー問題の応用
２部グラフの最大マッチング
画像の２値化
2部グラフ最大マッチングを最大パスアルゴリズムで解く
u1
v1
u2
v2
u3
v3
u4
v4
2部グラフ最大マッチングを最大パスアルゴリズムで解く
s
u1
v1
u2
v2
t
u3
v3
u4
v4
パス：s, u1, v1, t が見つかる．このパス上の枝の向きを反転させる．
s
u1
v1
u2
v2
t
u3
v3
u4
v4
2部グラフ最大マッチングを最大パスアルゴリズムで解く
s
u1
v1
u2
v2
t
u3
v3
u4
v4
パス：s, u2, v2, t が見つかる．このパス上の枝の向きを反転させる．
s
u1
v1
u2
v2
t
u3
v3
u4
v4
2部グラフ最大マッチングを最大パスアルゴリズムで解く
s
u1
v1
u2
v2
t
u3
v3
u4
v4
パス：s, u4, v3, t が見つかる．このパス上の枝の向きを反転させる．
s
u1
v1
u2
v2
t
u3
v3
u4
v4
2部グラフ最大マッチングを最大パスアルゴリズムで解く
s
u1
v1
u2
v2
t
u3
v3
u4
v4
sからtへのパスは取れない．S={s, u2, u3, v2}
s
u1
v1
u2
v2
t
u3
v3
u4
v4
最大フロー問題の応用：画像の二値化問題
原画像
単純二値化
閾値による単純二値化
閾値
0.5
1
1
1
1
0.9 0.7 0.7 0.2
1
1
1
0
0.5 0.3 0.4 0.4
1
0
0
0
0.3 0.3 0.3 0.2
0
0
0
0
0.5 0.6 0.7 0.5
二値化画像の例
原画像
単純二値化
二値化画像の例
原画像
近傍を考慮した方法
二値化データの比較
単純二値化
近傍を考慮した方法
画像の二値化（近傍の考慮１）
総和
7.5
総和
7
行和
0.5 0.6 0.7 0.5
0.9 0.7 0.7 0.2
0.5 0.3 0.4 0.4
0.3 0.3 0.3 0.2
2.3
行和
2.5
行和
1.6
行和
1.1
0
1
1
1
0
0
1
1
0
0
0
2
行和
2
1
0
1
0
0
列和
列和
列和
列和
列和
列和
列和
列和
2.2
1.9
2.1
1.3
2
2
2
1
要求：
行和
二値化した後の行（列）和 ＝ 元の値の切り下げ or 切り上げ
⇒ いつでも要求を満たす二値化は可能か？
行和
2
行和
1
画像の二値化問題（近傍の考慮１）
画像の二値化（近傍の考慮１）
3/2
s
2/1
2/1
数値/数値は
2/1
1/0
0.5
0.6
0.7
0.5
0.9
0.7
0.7
0.2
上限/下限
s からt へ流量７以上の
フローがあるので、
流量７か８の整数値の
フローがある
3/2
3/2
0.5
0.3
0.3
0.3
0.4
0.3
0.4
0.2
2/1
2/1
8/7
t
© Copyright 2024 ExpyDoc
