ナップサック問題 クマさん人形をめぐる熱いドラマの結末.

Presentation on theme: "ナップサック問題 クマさん人形をめぐる熱いドラマの結末."— Presentation transcript:

1 ナップサック問題 クマさん人形をめぐる熱いドラマの結末

2 二人組の泥棒がクマの人形をナップサックの最大容量が７kgという条件の下で価値が最大になるように盗もうとしている
小さい方から２、３、４、５ｋｇ　 同じく１６、１９、２３、２８万円

3 1.まず１ｋｇあたりの価値を計算し、それの大きい順にナップサックに入れる
しかし、この方法ではクマの人形を分割しないと価値を最大化することができない この計算方法を貪欲アルゴリズムという

4 2.次に問題を小さく分割して解く方法を思いつく
　持っていく　　　　　　　　　　　　　　　　　　　　　　 　　　or 　持っていかない 　で２通りに分ける　 　　　　　　　　　持っていく　　　　　　　　　　　持っていかない 完全列挙法　　　　　　　　　　　　　　　　　　　　　　　　

5

6 違う点は緩和問題を用いて上界を得ることによって枝きりをすること
3.分枝限定法を用いて解くことを思いつく 分枝限定法・・・基本的には完全列挙法 　　違う点は緩和問題を用いて上界を得ることによって枝きりをすること 貪欲アルゴリズムで出した値は最適値よりも大きくならない 　　　　　　　　　　　このことを下界という

7 緩和問題・・・問題の条件を緩めて最適値 よりも大きい値を出す
緩和問題・・・問題の条件を緩めて最適値　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　よりも大きい値を出す 　これによって得られる値を上界という ・最適値は下界と上界でサンドイッチされている 　最大化問題の場合 　　　　　　　　　　上界（緩和） 　　　　　　　　　　　最適値 　　　　　　　　　　　下界（実行可能）　となる

8 上界と下界が一致していれば、それが最適値である保証が得られる
実際に上界を得るには？さらにこの場合の緩和問題とは？ 　最も簡単な方法は整数条件を外して線形計画緩和問題を考える

9 極小クマさん１体 合計４６．５万円 小クマさん１体 中クマさん半分 これが上界 ４６．５万円＞貪欲アルゴリズムで出した値３５万円 これが下界
極小クマさん１体　　　合計４６．５万円　　 　小クマさん１体　　　　　　 　中クマさん半分　　　　　これが上界 ４６．５万円＞貪欲アルゴリズムで出した値３５万円 　　　　　　　　　　　　　　　　これが下界 上界と下界が一致していないので、これが最適解である保証はない　 　　　　　　　　　　　　　ここでtreeを使う

10 上界 ４６．５万円 上界 ４２万円 分枝限定法による最適解の探索 上界（１９+２３＝４２万円）が 下界（４４万円）より小さいので
　　　　　　　　　　　　上界 　　　　　　　　　　　　　　　　　　　　４６．５万円 　　　　　　　　　　　　　　　　　　　上界　　　　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　 ４２万円　 　　　　　　　　　　　　　　　分枝限定法による最適解の探索 　　　　　　　　　　　　　　　　　　　　上界（１９+２３＝４２万円）が 　　　　　　　　　　　　　　　　　　　　下界（４４万円）より小さいので 　　　　　　　　　　　　　　　　　　　　右半分を調べる必要なし 　　　　　　　　　　　　４４万円（下界）　　　　　　　

11 兄貴はシャバに出たら工場から１００体のクマさんを盗むと言い出した しかし１００体になると分枝限定法が有効になるかどうかわからない
制限条件が整数である場合には動的計画法が有効ということに気づく 動的計画法・・・基本的には最適性の原理を用いて、小さな部分問題から解いていく方法 実際にさっきの問題で動的計画法を用いてみると

12 0 1 2 3 4 5 6 7 16 19 35 23 39 42 44 なし 極小 極小、小 極小、小、中 極小、小、中、大
動的計画法の計算図 　0 　1 　2 　3 　4　 　5 　6 　7 なし 極小 　16 極小、小 　19 　35 極小、小、中 　23 　39 　42 極小、小、中、大 　44

13 動的計画法の手順 手順１．対象物（クマさん）が１つもない場合から始める。ナップサックの容量によらず、持っている価値の合計がすべて０である自明な場合からスタートする 手順２．順に対象物の個数を増やしていきナップサックの容量別の価値の合計を計算する

14 ナップサック問題 n個のアイテムから成る有限集合N、おのおののアイテムi Nの重量　　と価値　　　、およびナップサックの重量の上限bが与えられたとき、アイテムの重量の合計がbを超えないようなアイテムの詰め合わせの中で、価値の合計が最大のものを求めよ

15 ナップサック問題の定式化 アイテムi( N)をナップサックに詰めるとき１、それ以外の時０になる０－１変数を使うと 最大化 条件
　最大化　　　　　　　　　 　条件 ある制約を満たす整数の組で線形関数を最大化（最小化）するものを見つける問題を、整数計画問題と呼ぶ　　　　　　　　　　　　　

16 貪欲アルゴリズムはきわめて簡単で、単位重量あたりの価値　　　/　　の大きいものから順にbを超えない限りつめていくだけ
この解法では最適解を得られる保証はないが、問題の制約を満たした解を常に生成する これによって得られた解の値は、最適値より小さいか、等しいことが保証されているので下界と呼ばれる 分枝限定法を得るためには、下界の他に常に最適値より大きいか、等しい値である上界が必要になる 上界は変数　　の整数条件を緩和した次の問題をとくことによって得られる

17 上界を求めるには 最大化 　　条件 　　ある制約を満たす実数の組で線形関数を最大化（もしくは最小化するものを見つける問題を線形計画問題と呼ぶ 　　ナップサック問題を線形計画問題に緩和したものは貪欲アルゴリズムと同じようにして簡単に求まる 　　単位重量あたりの価値の大きいものから順にｂを超えない限り詰めていく 　　緩和問題の場合には端数も許す

18 動的計画法part1 ある物がｋ種類しかなく、かつナップサックの重量の上限が しかないような部分問題を考え、そのときの最大値を とする
ある物がｋ種類しかなく、かつナップサックの重量の上限が　　しかないような部分問題を考え、そのときの最大値を　　　　　　　　とする 　　　　　　　　　　＝最大化 　　　　　　　　　　　　　条件 　　部分関係間の関係より、　　　　　　　　は次の再帰方程式によって計算可能である

19 動的計画法part2

20 動的計画法まとめ 再帰方程式を境界条件のもとで順次解いていくことによってナップサック問題の最適解をO(nb)時間で求めることができる
多項式オーダーに見えるが実は違う 擬似多項式空間アルゴリズムである ナップサック問題はNP困難ではあるが適切に設定された分枝限定法を用いることによって実用規模の問題も高速に解くことができる