システム最適化特論 担当：平田 健太郎 第9回 （6/8） １．グラフとネットワークにおける数理 ・ 組合せ最適化（2） 1 講義日程（予定） 4/13 １．グラフとネットワークにおける数理 ・ 輸送問題とLP 4/20 ・ シンプレックス法（１） 4/27 ・ シンプレックス法（２）, 双対問題 5/7 ・ 多項式時間アルゴリズム, 内点法（１） 5/11 ・ 内点法（２） 5/18 ・ 最短経路問題とダイクストラ法（１） 5/25 6/1 6/8 ・ 最短経路問題とダイクストラ法（２） ・ 組合せ最適化（１） ・ 組合せ最適化（２） 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. ２三馬 b. ２三銀成 c. ２五飛車打 d. ２六飛車打 ・ ・ ・ 分枝 a b c d ・ ・ ・ 12 a. ２三馬以下の展開を考える. 玉側の応手 a b c d 動ける場所は赤い部分. すべて 玉が取られるのでNG. 逃げる選 択はない. 攻め駒を取る. ２三馬の脅威を 取り除くには２三香しかない. 玉側の応手は ２三香の一択 13 ２三香以下の展開を考える. 再び王手をかける ２三銀成 ⇒ 玉で取られて攻め 駒がほぼ盤上から無くなる. 脈 なし. ２五飛車打 ⇒3四の銀を玉で取 られる. (４六に香はあるが）攻め が続かない. 脈なし. a. ２三馬ではだめそうなので, この手を考慮するのを止める. 枝刈り, 限定 14 最初の可能性 ・ ・ ・ １ステップ後 ・ ・ ・ 15 詰将棋 正解は ２二飛車打 同角 ２三馬まで （三手詰め） ２二飛車打 同香なら ３三馬まで ２二飛車打 ２三合駒なら やはり３三馬まで 守りの角と香の効き筋の焦点に飛車を打つのが好手 「焦点に捨て駒」の格言どおり 16 今、釣（つり＝高さ）が九寸、股（こ＝底 辺）が十二寸の勾股弦（こうこげん＝直角三 角形）がある。その内部に、図のごとく、直 径が等しい円を二つ入れる。円の直径を問う。 17 ナップサック問題へのアプローチ 𝑐𝑖 /𝑎𝑖 はアイテム 𝑖 の単位重さあたりの満足度を表すので, この順で若い方から選択するのが合理的. アイテムを 0 と 1 の間の小数個 （0.3個とか） 取ることが できれば, 欲張り法で解決. アイデア: 変数に関する 0 − 1 の制約を（連続値に）緩和した 問題を元に考えてみる. 18 連続緩和問題：0-1変数の定義域を実数区間[0,1]に拡大したもの 部分問題：一部の変数を0または1に固定したもの 𝑐𝑖 𝑐𝑗 ≥ , 𝑎𝑖 𝑎𝑗 𝑖 < 𝑗 が成り立っているとする. から連続緩和問題の最適解は 𝑥 = (1,2/5,0,0) 19 ナップサック問題の特徴 １．緩和問題の実行可能領域はオリジナルを 含むので，緩和問題の最適値は0-1計画 問題の最大値の上界を与える 𝑆 𝑆 𝑆 での最大値は 𝑆での最大値 と等しいか, より大きい. 暫定解の値が，部分問題の上界（緩和問題の最適値） よりも大きければ，それ以上考える必要なし 目的関数値 連続緩和問題の 最適値 (下記の上界） 0-1計画問題の 真の最適値 暫定値 (これまでに 分かっている最大値） 赤が緑よりも小さければ, 青が緑よりも大きいはずがない. 20 ナップサック問題の特徴 2. 実数最適解の非0-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
© Copyright 2024 ExpyDoc
