ナップサック問題クマさん人形をめぐる熱いドラマの結末二人組の泥棒がクマの人形をナップサックの最大容量が７kgという条件の下で価値が最大になるように盗もうとしている • 小さい方から２、３、４、５ｋｇ • 同じく１６、１９、２３、２８万円 1.まず１ｋｇあたりの価値を計算し、それの大きい順にナップサックに入れる • しかし、この方法ではクマの人形を分割しないと価値を最大化することができない • この計算方法を貪欲アルゴリズムという 2.次に問題を小さく分割して解く方法を思いつく持っていく or 持っていかないで２通りに分ける持っていく完全列挙法持っていかない 3.分枝限定法を用いて解くことを思いつく  分枝限定法・・・基本的には完全列挙法違う点は緩和問題を用いて上界を得ることによって枝きりをすること貪欲アルゴリズムで出した値は最適値よりも大きくならないこのことを下界という  緩和問題・・・問題の条件を緩めて最適値よりも大きい値を出すこれによって得られる値を上界という・最適値は下界と上界でサンドイッチされている最大化問題の場合上界（緩和）最適値下界（実行可能）となる上界と下界が一致していれば、それが最適値である保証が得られる • 実際に上界を得るには？さらにこの場合の緩和問題とは？最も簡単な方法は整数条件を外して線形計画緩和問題を考える  極小クマさん１体小クマさん１体中クマさん半分合計４６．５万円これが上界４６．５万円＞貪欲アルゴリズムで出した値３５万円これが下界上界と下界が一致していないので、これが最適解である保証はないここでtreeを使う上界４６．５万円上界４２万円分枝限定法による最適解の探索上界（１９+２３＝４２万円）が下界（４４万円）より小さいので右半分を調べる必要なし４４万円（下界）兄貴はシャバに出たら工場から１００体のクマさんを盗むと言い出したしかし１００体になると分枝限定法が有効になるかどうかわからない  制限条件が整数である場合には動的計画法が有効ということに気づく  動的計画法・・・基本的には最適性の原理を用いて、小さな部分問題から解いていく方法実際にさっきの問題で動的計画法を用いてみると動的計画法の計算図 0 1 2 3 4 5 6 7 なし 0 0 0 0 0 0 0 0 極小 0 0 16 16 16 16 16 16 極小、小 0 0 16 19 19 35 35 35 極小、小、中 0 0 16 19 23 35 39 42 極小、小、中、大 0 0 16 19 23 35 39 44 動的計画法の手順 • 手順１．対象物（クマさん）が１つもない場合から始める。ナップサックの容量によらず、持っている価値の合計がすべて０である自明な場合からスタートする • 手順２．順に対象物の個数を増やしていきナップサックの容量別の価値の合計を計算するナップサック問題  n個のアイテムから成る有限集合N、おのおののアイテムi Nの重量 Si と価値 Vi 、およびナップサックの重量の上限bが与えられたとき、アイテムの重量の合計がbを超えないようなアイテムの詰め合わせの中で、価値の合計が最大のものを求めよ  ナップサック問題の定式化  アイテムi(N)をナップサックに詰めるとき１、それ以外の時０になる０－１変数を使うと  x v s  iN 最大化条件  vi xi iN si xi  b iN i i i i 0,1 x 0,1   N i i ある制約を満たす整数の組で線形関数を最大化（最小化）するものを見つける問題を、整数計画問題と呼ぶ  貪欲アルゴリズムはきわめて簡単で、単位重量あたりの価値 vi / i の大きいものから順にbを超えない限りつめていくだけこの解法では最適解を得られる保証はないが、問題の制約を満たした解を常に生成するこれによって得られた解の値は、最適値より小さいか、等しいことが保証されているので下界と呼ばれる s     分枝限定法を得るためには、下界の他に常に最適値より大きいか、等しい値である上界が必要になる上界は変数 xi の整数条件を緩和した次の問題をとくことによって得られる上界を求めるには  最大化条件  vx  s x b 0  x 1  N iN iN i i i i i i ある制約を満たす実数の組で線形関数を最大化（もしくは最小化するものを見つける問題を線形計画問題と呼ぶナップサック問題を線形計画問題に緩和したものは貪欲アルゴリズムと同じようにして簡単に求まる単位重量あたりの価値の大きいものから順にｂを超えない限り詰めていく緩和問題の場合には端数も許す動的計画法part1  ある物がｋ種類しかなく、かつナップサックの重量の上限が  しかないような部分問題を考え、そのときの最大値を f k,  とする f k,  ＝最大化 ik1 vi xi 条件 i1 si xi   , k xi 0,1 i  1・・・部分関係間の関係より、 f k,  は次の再帰方程式によって計算可能である k 動的計画法part2 f k,   f k 1,  max f k 1, , vi  f k 1,  si  f 1,   0 v 1 0    sk s  ,   2・・・ k k 0    s1 s   b 1 n 動的計画法まとめ     再帰方程式を境界条件のもとで順次解いていくことによってナップサック問題の最適解を O(nb)時間で求めることができる多項式オーダーに見えるが実は違う擬似多項式空間アルゴリズムであるナップサック問題はNP困難ではあるが適切に設定された分枝限定法を用いることによって実用規模の問題も高速に解くことができる