KATOエンジニヤリング開発日誌

「アウトプット無きエンジニアにインプットもチャンスも無い」の精神で書いています

「なっとくアルゴリズム」を読んだ - 動的計画法 -

動的計画法は問題を小さく分割し、それらの部分問題を先に解くことで難しい問題を解く手法である。

前回、貪欲法で実行したナップザック問題について動的計画法で考えてみる。

www.kato-eng.info

動的計画法

再びナップザック問題

ナップザック問題を動的計画法のアルゴリズムで解くには、次のようなグリッドをイメージする。

1 2 3 4
ギター
ステレオ
ノートPC

縦の行は選べる商品を記載し、横の列はナップザックの収容力(1~4ポンド)を表している。

今回の盗める商品の情報は下記の通り。

商品 価値 重さ
ギター 1,500ドル 1ポンド
ステレオ 3,000ドル 4ポンド
ノートPC 2,000ドル 3ポンド

ギター行

ギター行の処理を行う。
これはギターをナップザックに入れようとしていることを意味しており、グリッドのセル毎に「ギターを盗むかどうか」という決断を下している。

  1. 1つ目のセルは1ポンド分の商品が入るナップザックで、ギターが1ポンドなので、このセルの値は1500ドルになる。
  2. 2つ目のセルは2ポンド分の商品が入るナップザックだが、現時点で商品がギターしか考慮しないので、2つ目のセルも1500ドルになる。
  3. 3つ目と4つ目のセルも同様の考えで1500ドルになる。
1 2 3 4
ギター 1500 1500 1500 1500
ステレオ
ノートPC

上記表の各行は、盗む商品の最大の価値に対して、現時点で最も有力な推定値を表している。
この時点で4ポンドのナップザックに入る最も高価な商品は金額にして1500ドルということになる。

ステレオ行

ステレオ行の処理を行う。
この行では盗む商品をステレオとギターから選ぶことができる。どの行でも、その行の商品か上の行の商品(部分問題として解決した商品群)を盗むことができる。

  1. 1つ目のセルは1ポンド分の商品が入るナップザックであり、1ポンド分の商品で最も価値の高いのは1500ドルのギターになる。この時点の1ポンドのナップザックに対する最大価値の推定値は1500ドルのままである。
  2. 2つ目と3つ目のセルも同様で最大価値の推定値は1500ドルのギターになる。
  3. ナップザックの収容力が4ポンドになるとステレオが収まる。ギターの代わりにステレオを盗むと3000ドルになる。
1 2 3 4
ギター 1500 1500 1500 1500
ステレオ 1500 1500 1500 3000
ノートPC

このように推定値が更新されていくのがわかる。

ノートPC行

ノートPC行の処理を行う。

  1. 1つ目と2つ目のセルのナップザックではギターしか入らないため、推定値は1500ドルのままとなる。
  2. 3つ目のセルの時点でギターとノートPCが選択肢に出てくる。ノートPCを盗んだ方が価値が高いので、ノートPCを盗むことにする。
  3. 4つ目のセルでは、現時点の推定値は3000ドルということになっている。しかし3つ目のセルの時点でノートPCを盗んで2000ドルとなっており、まだ1ポンド分の余裕がある。この時にナップザックが1ポンドのときの部分問題の解を利用すると、「2000ドル + 1500ドル」の3500ドルという推定値を得られ、現時点の推定値である3000ドルを超えることがわかる。

答えは次のようになる。

1 2 3 4
ギター 1500 1500 1500 1500
ステレオ 1500 1500 1500 3000
ノートPC 1500 1500 2000 3500

ナップザック問題のFAQ

品物を追加する

盗める商品の品目を増やすことができるかを考える。

商品 価値 重さ
ギター 1,500ドル 1ポンド
ステレオ 3,000ドル 4ポンド
ノートPC 2,000ドル 3ポンド
iPhone 2,000ドル 1ポンド
1 2 3 4
ギター 1500 1500 1500 1500
ステレオ 1500 1500 1500 3000
ノートPC 1500 1500 2000 3500
iPhone

盗める商品にiPhoneを追加した。

  1. 1つ目のセルは1ポンド分の商品が入るナップザックで、これまでの最大値は1500ドルだったがiPhoneを盗むことで2000ドルに推定値が更新される。
  2. 2つ目のセルは2ポンド分の商品が入るナップザックで、これまでの推定値は1500ドルだったが、1ポンドのiPhoneを盗んでまだ1ポンドの余裕があるのでギターも盗む。この時点で推定値は3500ドルになる。
  3. 3つ目のセルでもiPhoneとギターを盗む方がよいので3500ドルが推定値となる。
  4. 4つ目のセルではiPhoneを盗むと3ポンド分の余裕があるが、3ポンドには2000ドルの価値がある。これらを足すと4000ドルになり、推定値が更新される。
1 2 3 4
ギター 1500 1500 1500 1500
ステレオ 1500 1500 1500 3000
ノートPC 1500 1500 2000 3500
iPhone 2000 3500 3500 4000

行の順番を変更する

行の順番を変更することで最大の推定値が変化することがありえるかを考える。

1 2 3 4
ステレオ 0 0 0 3000
ノートPC 0 0 2000 3000
ギター 1500 1500 2000 3500

最終的な最大推定値は変化しない。