動的計画法
分割統治法と動的計画法
アルゴリズムを設計する際には、まず全体をいくつかの小問題に分解して、その一つ一つを解いていくことにより全体の解を得る方法があります。このような手法を、分割統治法(divid and rule)と言います。
この方法は、ある程度複雑な問題を解く際には妥当な方法であるような感じがします。しかし、現実問題として、この方法には大きな欠点があります。なぜなら、実際に運用してみると、同じ問題を何回も解かなくてはならないようなケースに遭遇するからです。
そこで、「実際に必要とされるかどうかはわからないが、必要になりそうな小問題をあらかじめ解いておいて保存しておき、必要なときに取り出して使う、というアプローチも存在します。これが動的計画法(dynamic programming)の考え方です。
アプローチの方法の違い
一見似たように感じられる、動的計画法と分割統治法ですが、大きな違いは問題に対するアプローチの方法にあります。分割統治法では、与えられた問題を細かく分割して、分割した問題を解くことにより、最終的にはその大問題を解いたことになるようなタイプが適しています。
例を挙げるなら、クイックソートやマージソートなどといった、ソートアルゴリズムがその典型です。それに対し、動的計画法はその逆で、まず小さな問題を解き、その結果を積み上げながら、最終的な結果を得るというものです。前者がトップダウンだとするならば、動的計画法はボトムアップのアプローチと言えるでしょう。
動的計画法の適用条件
このように、大変有効に見える動的計画法ですが、その効力を発揮できるようにするには、必要な条件が、大きく分けて二つあります。
- 与えられた問題が、小問題に分割できること
- 分割した小問題の数が、多すぎないこと
特に大事なのが、2.です。動的計画法は、先に問題を解いておき、それを保存しておくという方法であることから、この条件が満たされなければ、最初の小問題を解くのに時間がかかりすぎる上に、場合によっては、ほとんど利用しない小問題を大量にメモリに保存することになるため、かえって効率が悪くなります。このような場合は、素直に分割統治法を使ったほうが賢明であるといえるでしょう。
ナップザック問題
ナップザック問題とは
ここからは、動的計画法を具体的な問題に当てはめてみます。もっとも有名な問題が、今から紹介するナップザック問題(knapsack problem)です。
商人が、行商に出かけると仮定します。このとき、行商人はできる限り価値の高い商品を売って、大きな売り上げを上げたいと考えているのですが、問題は商品を詰め込むことができるナップザックには、容量に限界があり、1000gしか商品を入れられないと仮定します。この時、商品と、その値段と重さの組み合わせが以下のようだったと仮定します。（表5-1.）
表5-1.商品と重さ・値段の組み合わせ| 1 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|
| 商品名 | お茶 | 野菜 | 豚肉 | 米 | 牛肉 |
| 重さ | 200g | 300g | 500g | 700g | 900g |
| 値段 | 200円 | 400円 | 700円 | 1100円 | 1400円 |
単純に考えれば、利益だけを追求するためには、牛肉をたくさん詰め込めばよさそうですが、ナップザックの容量の残りは100gとなります。では、軽いものを大量に入れればどうかと言うと、こちらも、お茶を5つ入れれば1000gになりますが、値段は200円×5=1000円で、牛肉ひとつにも値しません。
こういったときに、様々な商品を組み合わせて、いかに限られた条件下で、最大限の成果を上げるかを考えなくてはならないような問題が、ナップザック問題なのです。
これを一般化するととは、「N種類の品物があり、それぞれの大きさと価値が決まっているとき、大きさの合計がM以下で、価値の合計が最大になるような品物の組み合わせを求める」という問題ということになります。
問題の解法
では、実際に、この問題を動的計画法で解く方法を考えましょう。この問題を解くためには、商品1のみを使用したとき、商品1,2を使用したとき、…そして、最後に、1,2,3,4,5を使用したときの、商品の重さと、値段の合計、さらに最後に入れた商品の番号という表を作成してみます。なお、商品0は、商品がない状態を表すことにします。
問題では、ナップザックの最大の容量が1000gと言っていますので、これらの商品を組み合わせ、その重さが1000g以下になるの組み合わせを考えていきます。最大容量が1000gだからといって、1000gちょうどの時に最大の価値になるとは限りません。そこで、1000g以下の組み合わせの中から、価値が最大になる組み合わせを探す必要があります。
では実際に、それを表にしたものを見てみましょう。
(1) 商品1のみを使用| ナップザックの容量 (×100g) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 値段の合計 (×100円) | 0 | 0 | 2 | 2 | 4 | 4 | 6 | 6 | 8 | 8 | 10 |
| 最後に入れた 品物の番号 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
続いて、この問題を基にして、商品1,2のみを使用したときの場合も考えてみます。同じ容量のナップザックに対して、より大きい数値を得られるような組み合わせが存在する場合は、そこでの値段の合計を更新します。
(2) 商品1,2のみを使用| ナップザックの容量 (×100g) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 値段の合計 (×100円) | 0 | 0 | 2 | 4 | 4 | 6 | 8 | 8 | 10 | 12 | 12 |
| 最後に入れた 品物の番号 | 0 | 0 | 1 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 |
以下、同様の処理を繰り返していきます。
(3) 商品1,2,3のみを使用| ナップザックの容量 (×100g) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 値段の合計 (×100円) | 0 | 0 | 2 | 4 | 4 | 7 | 8 | 9 | 11 | 12 | 14 |
| 最後に入れた 品物の番号 | 0 | 0 | 1 | 2 | 1 | 3 | 2 | 3 | 3 | 2 | 3 |
(4) 商品1,2,3,4のみを使用
| ナップザックの容量 (×100g) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 値段の合計 (×100円) | 0 | 0 | 2 | 4 | 4 | 7 | 8 | 11 | 11 | 13 | 15 |
| 最後に入れた 品物の番号 | 0 | 0 | 1 | 2 | 1 | 3 | 2 | 4 | 3 | 4 | 4 |
(5) 商品1,2,3,4,5使用
| ナップザックの容量 (×100g) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 値段の合計 (×100円) | 0 | 0 | 2 | 4 | 4 | 7 | 8 | 11 | 11 | 14 | 15 |
| 最後に入れた 品物の番号 | 0 | 0 | 1 | 2 | 1 | 3 | 2 | 4 | 3 | 5 | 4 |
(1)～(5)で、各プロセスで見つかった値段の合計の最大値を記憶しておき、残った値段が、求める価格になります。
これで、すべての組み合わせを算出できました。興味深いのは、全ての商品を詰め込んでいったからと言って、最大限の価値を得られるとは限らないという点です。最大の値段は、1500円だということがわかりますが、この場合、商品5が必要がないということがわかります。
ナップザック問題の実装とメモ化再帰
基本の考え方
次に、ナップザック問題の実装について考えてみましょう。前述の通り、ナップザック問題を解くためには、商品1、商品1と2、…といった各組み合わせの場合の商品の数、価値、重さの組み合わせの表を作る必要があります。プログラムは、まずそれぞれの表を作ることによって成立しています。
まず、最初の表、(1)を作るケースを考えてみましょう。このケースは非常に単純で、ナップザックの容量を100gずつ増やしていった時、そこに何個の荷物1が入るのか、を見ていけばよいので、表は容易に完成します。
続いて、(2)を作るケースを考えてみます。このとき、動的計画法の考え方より、(1)の表をベースにして考えます。商品2の重さは、300gですから、どんなに少なくても、リュック容量は300gから始まります。ここで、商品1,2の組み合わせで、値段が最大になるものを探し出し、(1)の結果よりも大きければ、値を入れ替えます。
ナップザック問題の計算量
では、ナップザック問題の計算量はどのくらいになるでしょう？品物の種類をn、ナップザックの大きさをmとすると、O(mn)になります。ただ、気をつけなくてはならないのは、これが一般的な動的計画法の一般的な計算量ではないということです。動的計画法の計算量は、その問題に依存します。
 |  |  |
