ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム Part 4 組合せ最適化，4.1 節 分枝限定法 pp. 105-110 補助資料：組合せ最適化短編集（朝倉書店） ナップサック問題（クマさん人形泥棒のお話） • Part 4では組合せ最適化の種々の技法を解説 • ここでは，0-1ナップサック問題を例として分枝限 定法についてを解説． 4.1節 分枝限定法 1 NP-困難な組合せ最適化問題 に対するアプローチ • NP-困難（完全）な問題は難しい（1.5節巡回セー ルスマン問題，pp.18-26参照） • 最悪の場合の計算時間が多項式時間（＝高速 の意味）で（おそらく；P≠NPの仮定のもとでは）抑 えられない． • 最適解はあきらめずに，最悪の場合は多項式時 間で終わることを諦め．->厳密解法 • 多項式時間で終わることを保証し，最適解を諦 め．->近似解法 or ヒューリスティクス 4.1節 分枝限定法 2 0-1ナップサック問題 16万円 19万円 16 23万円 28万円 28 23 ７ｋｇ 2kg 3kg 極小 小 4kg 5kg 中 大 ナップサックの重量を超えないように，なるべく価値の高い クマさんをもって逃げるには，どれを持っていく？ 4.1節 分枝限定法 3 分枝限定法 列挙法，力ずく法（1.5節，巡回セールスマン問題参照） すべての可能性を列挙して，その中で最良のものを選択． 都市の数が n の巡回セールスマン問題に対しては n! かかった． Ｑ．クマさん n 体に対する0-1ナップサック問題の場合には? 分枝限定法 列挙木をすべて生成するのではなく，一部分だけを列挙すること でごまかすテクニック． 分枝（branch）：基本的に列挙木を生成する操作と同じ． 限定（bound）：列挙木のある点以降を探さなくても良いことを巧く 保証する．（道具は上界と下界） 4.1節 分枝限定法 4 (整数計画問題としての）定式化 クマさんの集合 N クマさんiの価値 vi クマさんiの重量 si ナップサックの重量制限 b 最大化 v x iN 条件 s x iN 変数 クマさんiをもっていくとき xi=1 そうでないとき xi=0 i i i i b xi 0,1 i N 4.1節 分枝限定法 5 列挙木 極小クマをもって逃げる 極小クマをおいていく 場合分けで考えてみよう！ 場合分けを 分枝と呼ぶ 35 万円 39 44 16 万円 万円 万円 42 万円 19 万円 23 28 0 万円 万円 万円 28万円 黒丸はナップサックが 破れてしまうことを表す 16万円 2kg 4.1節 5kg 分枝限定法 6 上界と下界 上界（実行可能） 上界（緩和） 最適値 最適値 下界（緩和) 下界（実行可能) 最大化問題の場合 最小化問題の場合 ナップサック問題は最大化問題なので， 実行可能解をもってくれば，それが下界． （たとえば，小クマだけもって逃げてもナップサックは破れないので 実行可能．小クマの価値19万円は下界（最適値は19以上）． 上界を得るには緩和問題を導入する必要がある！ 4.1節 分枝限定法 7 ナップサック問題の緩和問題 最大化 v x iN 条件 s x iN i i i i b 代わりに線形制約にする （線形緩和） xi 0,1 i N 0 xi 1 線形緩和問題の最適解は，整数にならないこともある． ＜クマさんを切っても（バラバラにしても）いい場合と解釈＞ ナップサック問題の線形緩和問題は，どん欲アルゴリズムで解ける． （単位重量あたりの価値 vi/si の大きい順に詰めていくだけ！） 4.1節 分枝限定法 8 線形緩和問題の最適解 （どん欲アルゴリズム） 16万円 19万円 23万円 28万円 28 23 16 ７ｋｇ 2kg 3kg 極小 単位重量あたりの価値 xi 4.1節 8 1 4kg 5kg 小 中 大 6.333 5.75 1 0.5 分枝限定法 5.6 この順に詰めていく！ 0 最適値=16+19+23/2=46.5 9 分枝限定法の探索 上界 46.5万円 上界 16 19 42万円 23 28 16 35 万円 39 16 44 万 円 2kg 3kg 4kg 5kg 万円 万円 ある時点での上界（極小クマをもっていかない場合の42万）が 既にわかっている下界（大と極小をもっていく場合の44万）以下 ならば，そこから先は探さなくてよい 4.1節 分枝限定法 10 分枝限定法の効率 下界，上界の性能に「強く」依存 ->多面体的アプローチ（4.2節）で線形計画緩和の強化 -> Lagrange緩和（4.3節）で良い上界（最小化のときは下界）を計算 -> 近似解法で良い下界（最小化のときは上界）を早めに算出 分枝する方法（分枝ルール）にも依存 例では，小さいクマさんから順に場合分けした． 他にも， •大きいクマさんを先に考える． •値段の高いクマさんを先に考える． •（値段÷大きさ）の大きいクマさんを先に考える． どの点を優先して分枝するか（分枝子問題選択ルール）にも依存 上界の大きいものから分枝（その下に良い解がある可能性大） 4.1節 分枝限定法 11
© Copyright 2024 ExpyDoc
