講義資料 (6/8)

システム最適化特論
担当:平田 健太郎
第9回 (6/8)
1.グラフとネットワークにおける数理
・ 組合せ最適化(2)
1
講義日程(予定)
4/13 1.グラフとネットワークにおける数理
・ 輸送問題とLP
4/20
・ シンプレックス法(1)
4/27
・ シンプレックス法(2), 双対問題
5/7
・ 多項式時間アルゴリズム, 内点法(1)
5/11
・ 内点法(2)
5/18
・ 最短経路問題とダイクストラ法(1)
5/25
6/1
6/8
・ 最短経路問題とダイクストラ法(2)
・ 組合せ最適化(1)
・ 組合せ最適化(2)
2
【クラスカル法の証明】
前提となる事実: 1) 節点数  のグラフの全域木の枝は  − 1 本
節点数: 6, 全域木の枝の本数: 5
(2+1+1+1+1=6)
2) 全域森の枝数はそのグラフに固有の定数
全域森 ⇒ グラフを連結成分に分解したとき
各連結成分に全域木
連結成分
全節点数 , 連結成分数  ならば, 全域森
の枝数は  − 
全域森の例
3
【クラスカル法の証明】
クラスカル法によって得られた全域木を
とする.
上の並び順で, 左の枝から順次, 加えていったとすると
という大小関係が成り立っている.
ここで より長さの小さい別の全域木
存在すると仮定する. また, 枝の長さは
が
であるとする.
ℓ1 よりも短い枝は存在しないから, ℓ1 ≤ 1 である.
4
いま ℓ1 ≤ 1 であるが,  = 2, ⋯ ,  − 1 の全ての  について ℓ ≤ 
とはならない.
もしそうであれば,  ∗ の長さの方が  よりも短くならないから.
If ℓ ≤  for  = 1, ⋯ ,  − 1 , then  =
したがって,
−1
 ℓ

≤ ∗ =
−1
 

となる が必ず存在するので, そのうち最小のものを
 とする.
ℓ1 ≤ 1
ℓ−1 ≤ −1
ℓ > 
枝の集合
からなる部分グラフ
 − 1本
本
を考える
(枝の重複はあり得る)
5
枝の集合
を考える.
からなる部分グラフ
の性質
枝の重複はあり得るが, 前半は  − 1 本, 後半は  本だから, 前後半が全て
重複していることはありえない.
からなる部分グラフを ℓ とすると, ℓ と  は異なる.
枝集合
(直感的に言えば,  の枝集合 の方が大きい. )
の構成法から, ℓ は
全域森:
に対する全域森になる. まずこれを示す.
木の集合(森)であって, これ以上, グラフに含まれるどの枝を
付け加えても, 閉路ができてしまうもの
6
ℓ が  の全域森でないとする.
ℓ に対して, 現在 ℓ を構成している枝以外の  の枝を加えても, 閉路に
ならないようにできる. ( ℓ ≠  だから確かにそのような枝はとれる. )
その枝は
より短い.
のいずれかであるが,
であるので, その長さは
 を構成する途中で ℓ に枝を追加する際,  の枝から閉路を生じない最小
長さの枝 ℓ を選んだはずである.
ℓ よりも短い  の枝を選んで, 閉路にならないようにできるのは矛盾.
だから ℓ は全域森である.
7
ℓ はの全域森である.
ℓ の枝数は  − 1 である.
全域森は各連結成分に対する全域木から構成される.
全域木よりも枝数の多い木は存在しない.
全域森よりも枝数の多い森は存在しない.
 は  本以上の枝をもつ森は含まない.
一方,  ≔ 1 , ⋯ ,  は  に対する全域木  ∗ の一部を構成する森であって
 の一部でもある. 枝数は . よって  が枝数  の森を含んでいることになり,
これは矛盾である.
 より長さの小さい別の全域木は存在しない.
 は最小木
8
最小木問題は, 欲張り法の一種であるクラスカル法
で簡単に解けてしまう, 特殊な組合せ最適化問題
NP困難な組合せ最適化問題に対しては, 統一的な
効率のよいアルゴリズムは知られておらず, 個別に
工夫を凝らすしかない
9
 ナップサック問題
に対して有効なアプローチ
分枝限定法 (branch-and-bound method)
実行可能解を列挙するための場合分けの過程で,最適解が
得られる見込みのない不必要な場合分けをできるだけ省略
し,探索範囲を絞り込む
10
分枝限定法
通常組合せ問題では, 場合
分けを木構造で表現し, 深さ
方向, 幅方向に探索していく
⇒ 分枝
ある地点よりも下に最適解が
ないと判断できれば, 以下の
探索を打ち切る
⇒ 枝刈り, 限定
11
詰将棋
王手になる選択
a. 2三馬
b. 2三銀成
c. 2五飛車打
d. 2六飛車打
・
・
・
分枝
a
b
c
d
・
・
・
12
a. 2三馬以下の展開を考える.
玉側の応手
a
b
c
d
動ける場所は赤い部分. すべて
玉が取られるのでNG. 逃げる選
択はない.
攻め駒を取る. 2三馬の脅威を
取り除くには2三香しかない.
玉側の応手は
2三香の一択
13
2三香以下の展開を考える.
再び王手をかける
2三銀成 ⇒ 玉で取られて攻め
駒がほぼ盤上から無くなる. 脈
なし.
2五飛車打 ⇒3四の銀を玉で取
られる. (4六に香はあるが)攻め
が続かない. 脈なし.
a. 2三馬ではだめそうなので,
この手を考慮するのを止める.
枝刈り, 限定
14
最初の可能性
・
・
・
1ステップ後
・
・
・
15
詰将棋
正解は
2二飛車打
同角
2三馬まで (三手詰め)
2二飛車打
同香なら
3三馬まで
2二飛車打
2三合駒なら
やはり3三馬まで
守りの角と香の効き筋の焦点に飛車を打つのが好手
「焦点に捨て駒」の格言どおり
16
今、釣(つり=高さ)が九寸、股(こ=底
辺)が十二寸の勾股弦(こうこげん=直角三
角形)がある。その内部に、図のごとく、直
径が等しい円を二つ入れる。円の直径を問う。
17
 ナップサック問題へのアプローチ
 / はアイテム  の単位重さあたりの満足度を表すので,
この順で若い方から選択するのが合理的.
アイテムを 0 と 1 の間の小数個 (0.3個とか) 取ることが
できれば, 欲張り法で解決.
アイデア: 変数に関する 0 − 1 の制約を(連続値に)緩和した
問題を元に考えてみる.
18
連続緩和問題:0-1変数の定義域を実数区間[0,1]に拡大したもの
部分問題:一部の変数を0または1に固定したもの
 
≥ ,
 
 <  が成り立っているとする.
から連続緩和問題の最適解は  = (1,2/5,0,0)
19
 ナップサック問題の特徴
1.緩和問題の実行可能領域はオリジナルを
含むので,緩和問題の最適値は0-1計画
問題の最大値の上界を与える


 での最大値は での最大値
と等しいか, より大きい.
暫定解の値が,部分問題の上界(緩和問題の最適値)
よりも大きければ,それ以上考える必要なし
目的関数値
連続緩和問題の
最適値 (下記の上界)
0-1計画問題の
真の最適値
暫定値 (これまでに
分かっている最大値)
赤が緑よりも小さければ,
青が緑よりも大きいはずがない.
20
 ナップサック問題の特徴
2. 実数最適解の非0-1要素は1つしかないので, 0要素の
どれかを1とすれば0-1計画問題の近似解が直ちに得られる.
(欲張り法!)
実数最適解
0-1近似解
暫定目的関数値 8
21
分枝限定法
分枝操作:自由変数のひとつを0または1に固定して,
新しい部分問題を生成
限定操作:部分問題の終端ができる場合に,その部分問題を
解くことをやめる
終端条件:
1. 部分問題の上界値が暫定値より小
2. 連続緩和問題の最適解が0-1解
3. 部分問題が実行可能解をもたない
22
x1
1
0
x2
x3
x4
0
0
1 0
0
1
1
0
1 0
1
1
0
0
1
1 0
0
1 0
1 0
1 0
1
1 0
1
分枝図
23
x1
1
0
x2
x3
0
x4
0
1 0
0
1
1
0
1 0
1
1
0
0
1
1 0
0
1 0
1 0
1 0
1
1 0
1
24
x1
1
0
x2
x3
x4
0
0
1 0
0
1
1
0
1 0
1
1
0
0
1
1 0
0
0
1 0
1 0
1
1 0
1
25
x1
1
0
x2
x3
x4
0
1
1
0
0
0
1 0
1 0
1
1 0
1
26
x1
1
0
x2
x3
x4
0
1
1
0
0
0
1 0
1 0
1
1 0
1
27
x1
1
0
x2
x3
x4
1
0
最適解
1
0
0
1 0
1
28