動的計画法の易しい解説

動的計画法とは、ある問題を複数の小さな問題に分割し、それぞれの問題を解決することで、全体の問題を解決する方法です。動的計画法は、複雑な問題を解決するために使用される一般的なアルゴリズムであり、コンピュータサイエンスや数学、経済学などの分野で広く使用されています。

動的計画法は、1950年代にリチャード・ベルマンによって考案されました。当初、彼は航空機の制御問題に取り組んでいたため、この手法は最適制御問題に対する解法として発展していきました。その後、他の最適化問題にも応用され、現在では幅広い分野で使用されています。

動的計画法は、以下の3つのステップで構成されます。

  1. 最適化問題を小さな部分問題に分割する
  2. 各部分問題を解決する
  3. 各部分問題の解を組み合わせて、全体の問題を解決する

動的計画法の具体例

例えば、以下の問題を考えてみましょう。「n個のアイテムがあり、それぞれの価値と重さが与えられています。重さの合計がwを超えないように、最大の価値を持つアイテムの組み合わせを見つけてください。」

この問題は、動的計画法を用いることで効率的に解くことができます。まず、部分問題を考えます。例えば、i個目までのアイテムから重さの合計がj以下になるように選んだ場合の最大価値を、f(i,j)とすると、次のような再帰的な式が成立します。

f(i,j) = max{ f(i-1,j), f(i-1,j-w[i])+v[i] }

この式について具体的に説明すると、f(i,j) は「i番目までのアイテムから重さの合計がj以下になるように選んだ場合の最大の価値」という意味です。つまり、i番目のアイテムを選ぶか選ばないかを判断して、最大の価値を求めることができます。

式の右辺には、二つの項があります。f(i-1,j) は「i-1番目までのアイテムから重さの合計がj以下になるように選んだ場合の最大の価値」であり、f(i-1,j-w[i])+v[i] は「i番目のアイテムを選んで重さが w[i] だけ増えた場合の最大価値」という意味です。ここで、v[i] は i 番目のアイテムの価値、w[i] は i 番目のアイテムの重さを表しています。

max{ } は、括弧内の二つの値のうち、大きい方を選ぶことを表します。つまり、式全体は、「i-1番目までのアイテムから重さの合計がj以下になるように選んだ場合の最大の価値」と「i番目のアイテムを選んで重さが w[i] だけ増えた場合の最大価値」のうち、より大きい方を f(i,j) として選択するということになります。

この式を使って、ナップサック問題を解く例を挙げることができます。 ナップサック問題は、与えられた一定の容量のナップサックに、価値の異なる複数の品物を入れていくつかの制約条件の下で、価値の合計を最大化する問題です。

例えば、容量が W=10 で、品物が以下のように与えられた場合、

品物 重さ 価値
1 2 3
2 3 4
3 4 5
4 5 8

f(i,j) の値を以下のように計算することができます。

  • f(0,j) = 0 (品物を選ばない場合は、価値は0になります)
  • f(i,0) = 0 (重さが0の場合、価値は0になります)
  • f(1,j) = 3 (品物1を選んだ場合の最大の価値は3になります)
  • f(2,j) = max{f(1,j), f(1,j-w[2])+v[2]} (品物2を選ぶか選ばないかを判断する)
  • f(3,j) = max{f(2,j), f(2,j-w[3])+v[3]} (品物3を選ぶか選ばないかを判断する)
  • f(4,j) = max{f(3,j), f(3,j-w[4])+v[4]} (品物4を選ぶか選ばないかを判断する)

最終的に f(4,10) = 12 となり、この場合、最大の価値は12になります。このように、動的計画法を用いることで、ナップサック問題を効率的に解くことができます。

以上が、動的計画法の解説です。動的計画法は、複雑な問題を解決するための一般的な手法であり、コンピュータサイエンスや数学、経済学などの分野で広く使用されています。

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 [ 米田優峻 ]