動的計画法 / Python DP

プログラム基礎同演習

Transcript

1. 1 動的計画法 プログラミング基礎同演習 慶應義塾大学理工学部物理情報工学科 渡辺 2019/12/17
2. 2 組み合わせ最適化問題の解法 ・貪欲法 ・全探索 ・メモ化再帰による動的計画法
3. 3 レストランにいって、料理や飲み物の注文をしたい できることなら美味しいものを食べたい vs. でもカロリーや値段は低く抑えたい 許容予算内、カロリー内で、「幸せ度」 を最大化する最適化問題になっている
4. 4 一定の制約条件下で コストを最小化する or 価値を最大化する ように、何かの組み合わせや順番を決める問題
5. 5 ・スーパーで買い物をする ・図書館に本を返却する ・郵便局で手紙を出す あなたは以下の三つのタスクをこなす必要がある 自宅 図書館 郵便局 スーパー スーパー、図書館、郵便局は自宅から等距離にある どのような順序でこなすべきか？
6. 6 もし「スーパー」「郵便局」「図書館」の順番だと・・・？ 持ち物 買い物をする 手紙を出す 本を返す 重い本を持ったまま3ステップ 買い物袋を抱えたまま3ステップ
7. 7 持ち物 買い物をする 本を返す 手紙を出す もし「スーパー」「郵便局」「図書館」の順番だと・・・？ 重い本を持つのは1ステップ 買い物袋持つのも1ステップ
8. 8 鉄板の型抜き (長方形詰込問題) 配送順序 塗装計画 白→黒：そのまま塗装できる 黒→白：洗浄が必要 バイトのシフト作成
9. 9 組み合わせ最適化問題の解法 ・貪欲法 ・全探索 ・メモ化再帰による動的計画法 これをナップサック問題を題材に考えてみる
10. 10 重さ 価値 3 4 3 33 36 24 持てる重さは最大「10」まで 5 50 持ち運べる範囲で価値を最大化したい 制約条件
11. 11 貪欲法は組み合わせ最適化問題の近似解を与える手法 ・選べる選択肢に、なんらかの方法で順番付けをする ・制約条件を満たす限り、上から順に選ぶ 計算量は ※ 多くの場合、貪欲法はわりと良い解を与える ↑ソートが一番重い
12. 12 重さ 価値 4 3 36 24 5 50 重さあたりの価値 10 9 8 3 33 11 上から順番に選ぶ ここで重さ10を超えるため ストップ 貪欲法による解 最適解 重さ8 価値 83 重さ10 価値 93
13. 13 を入れる を入れない を入れる を入れない を入れる を入れない
14. 14 各品物について「入れる」か「入れない」かを選ぶ 品物の数をNとして 通り 計算量は ※ N=20なら余裕、がんばればN=30くらいまで？
15. 15 貪欲法：簡単だが近似解しか得られない 全探索：厳密だが計算量が膨大 動的計画法：厳密で、かつ効率的
16. 16 Dynamic Programming, DP 動的計画法が適用できる条件 ・大きな問題を小さな問題に分解できる(分割統治) ・小さな問題の結果が再利用可能である(メモ化)
17. 17 目的地になるべく安く、早く着きたい → 最短経路問題 現在地から目的地まで複数の経路がある
18. 18 A B C D E F G H I 2 7 8 1 2 3 15 10 12 1 3 2 各辺に重み(コスト)が設定されているグラフがある A I から まで行きたい その際、辺のコストの合計を最小にしたい
19. 19 最短経路 コストの合計：13 A B C D E F G H I 2 7 8 1 2 3 15 10 12 1 3 2 この解をどうやって(効率的に)求めるか？
20. 20 A E I 3 10 もし最短経路が「A – E – I 」という経路であれば AからIに含まれる 「AからE」への経路 「EからI」への経路 もそれぞれ最短
21. 21 A E I 3 10 2 もしA-Eに、より低コストな経路があったら？ A-Eの経路としてそちらを選んだ方がトータルコストが下がる A-E-Iが最短経路であることに矛盾 最短経路に含まれる任意の二点間経路は最短
22. 22 A B C D E F G H I 1 2 いま、「部分問題」が解けているとする AからGへの最短経路 AからHへの最短経路 がそれぞれわかっている
23. 23 「AからG」「AからH」までの最短経路のコストが わかっているなら、この問題を解けばよい A G I 1 2 13 11 H 「A-H-I」が最短経路であることがわかる A B C D E F G H I 2 7 8 1 2 3 15 10 12 1 3 2 全体像はいったん忘れる
24. 24 A B C E F H 2 7 1 2 3 12 3 AからHに行く最短経路は？ AからEに行く最短経路(3) AからFに行く最短経路(8) A E H 12 3 3 8 F がわかっているなら 全体像はいったん忘れる 「A-F-H」が最短経路であることがわかる この問題↓を解けばよい
25. 25 解きたい問題の「部分問題」が全て解けているなら 全体の最適解が得られる 小さい部分問題から順番に解いていく A B C D E F G H I 2 7 8 1 2 3 15 10 12 1 3 2 AからBへの最短経路 AからCへの最短経路・・・
26. 26 A G I 1 2 13 11 H 最短経路のコストは13とわかっているとする 最終目的地 「I」に至る経路は「G」か「H」か？ A-H のコストと H-Iのコストの和 = 13 A-G のコストと G-Iのコストの和 = 14 「A-G」「A-H」までの最短コストから計算してみればよい H経由だった
27. 27 世の中は最適化問題に溢れている 組み合わせ最適化問題を厳密に解くのは困難 近似解を高速に得る方法がある(貪欲法等) 動的計画法は ・大きな問題が小さな問題に分解できる ・小さな問題の結果が再利用できる ことを利用して、効果的に厳密解を得る
28. 28 N円持ってサイゼリヤに行ったら 最大でどれだけカロリーを摂取できるか？ ・同じメニューを二度選んではいけない ・ドリンクバーやガムシロップ等も禁止 条件 ※ メニュー「幸せ度」はカロリーに比例すると近似する
29. 29 彩りガーデンサラダ 小エビのサラダ やわらかチキンのサラダ イタリアンサラダ ・・・ 299 円 349 円 299 円 299 円 130 kcal 115 kcal 134 kcal 92 kcal 0.435 kcal/円 0.330 kcal/円 0.448 kcal/円 0.307 kcal/円 ラージライス アーリオ・オーリオ (W) ・・・ 219 円 574 円 454 kcal 1120 kcal 2.07 kcal/円 1.95 kcal/円 「価格あたりのカロリーが高い順」に並べる 一番上から、予算が許す限り選ぶ 品目 価格 カロリー 価格あたりの カロリー
30. 30 全探索は「トーナメント式」 「予算オーバー」なら不戦敗 予算内なら総カロリーが高い方が勝ち あるメニューを選ぶ場合 選ばない場合
31. 31 n 番目までのメニューの範囲で、 budget 円以下で最大のカロリーを返す関数 全探索の関数はこんな形をしていた search(n, budget) 同じ(n, budget)を与えられたら、同じ値を返すはず 一回計算したら、次から再利用できる(メモ化)
32. 32 n 番目までのメニューの範囲で、 budget 円以下で得られる最大のカロリー 計算が終わって得られる辞書 の情報が入っている dic[(n, budget)] には、
33. 33 もしbudget 円以下で得られる最大カロリーメニューに n番目のメニューが入っていなければ dic[(n-1, budget)] dic[(n, budget)] これらが等しくなるはず この事実を利用して、再帰的に「最大カロリーメニューに このメニューが含まれるか」を調べていく