ACM-ICPC

動的計画法



動的計画法(Dynamic Programing)は、国内予選レベルではおそらく知らなくてもだいじょーぶです。しかし、4問以上を目指しているのなら、おさえておいた方がいいかもしれません。
というか、あまり上手く説明できないかも。

概要

ここで言う動的計画法は、簡単に言うと、いつ計算しても同じになる値をどこかにとっておいて
いつでも呼び出せるようにすることで、重複計算を避けようという考え方です。

私の経験から言わせてもらえば、次のような問題に適応することで効果的な場合が多いです。
・元の問題を小さな部分問題に分割できる。
・その部分問題の答えからもとの問題の答えを導ける。(小さいほうから順番に計算できる)
・一番小さな部分問題はすぐに解ける。
・小さいほうの部分問題は何回も呼び出される。
・状態数がそんなに大きくない。(大きくないの基準は問題による。)

これについては後で述べるとして、例を見てみましょう。

例題

整数を分割する問題。

整数nが与えられる。1<=n<100である。これの分割数を求めよ。
分割数とは、nを正の整数の和で何通りに表せるかで、例えば6なら、
[6] [5,1] [4,2] [4,1,1] [3,3] [3,2,1] [3,1,1,1]
[2,2,2] [2,2,1,1] [2,1,1,1,1] [1,1,1,1,1,1]
があるので、答えは11となる。

まずバックトラックでプログラムを作ってみます。
ある数nをa以下の数だけで表す方法をpart(n,a)と定義しましょう。

これには2通りあって、aを本当に使う場合と使わない場合があります。
aを使わない場合は簡単で、aを使わない、つまりa-1以下で足りているのだから、単にpart(n,a-1)となります。aを使ったら、残りはn-aで、しかもまだaを使えるので、つまりpart(n-a,a)ですね。n>=aのときは、これを加算することになります。

まとめると次のようになります。
int part(int n, int a)
{
 int ret;
 if(n == 0 || a == 1)
   return 1;
 ret = part(n, a-1);
 if(n >= a)
   ret += part(n-a, a);
 return ret;
}

nが0のときは分割しきったということで、またaが1のときは[1,1,...]しかないということで、答えが一つ見つかったので1を返し、他の場合は上の説明の通りに計算しています。バックトラック法で述べた終了条件というのを思い出してください。

呼び出しは、元の問題つまり「nをn以下で分割する方法は何通りか」なので、こうなるでしょう。

answer = part(n, n);

このプログラムの無駄なところは、nやaが小さいところの計算がいろんなところで何回も呼び出されているところです。そこで動的計画法を適応してみましょう。

part(int m)
{
 int p[100][100];
 int n, a;
 for(a = 0; a <= m; a++)
   p[0][a] = 1;
 for(n = 0; n <= m; n++)
   p[n][1] = 1;
 for(n = 1; n <= m; n++){
   for(a = 2; a <= m; a++){
     p[n][a] = p[n][a-1];
     if(n >= a)
       p[n][a] += p[n-a][a];
   }
 }
 return p[m][m];
}

part(n,a)をpart[n][a]に置き換え、数値が小さいほうから順に計算しています。一番小さいところでは、直接値を入れています。そして元の問題は、「mをm以下の数で分割する方法は何通りか」なので、p[m][m]を返します。

例題2

もう少し簡単な、1次元配列でできる問題に挑戦してみましょう。

ある古代ピラミッドの王室には、財宝が詰まった箱が100個一列に並んでいる。
トレジャーハンターのMimutea氏は、そのありかをついに突き止めた。
箱に入っている財宝の価値はまちまちで、1〜10000までの評価がつけられる。
彼は合計の価値をできるだけ多く持ち帰りたいが、2つの連続した箱を取り去ると
王室に仕掛けられたトラップが発動して閉じ込められてしまうことがわかっている。
全ての宝箱の価値が与えられたとき、最高でどれくらい持ち帰れるかを
計算するプログラムをつくりなさい。

ん、どっかでみたような…。箱の数が10倍に増えてるけど…。

この問題で表に格納するのは、その場所が選んだ箱の中で一番右であるときの最大値。
つまりp[2]には、[] [0] [1] [2] [0,2]の5種類の取り方の中の最大値が入るわけです。

こう定義すると、p[i]は次のうち一番大きいものとなります。
case 1: p[i-1] ←箱iは取らなかった
case 2: p[i-2]+t[i] ←箱iを取った(その前に取ったのは2つ前)
case 3: p[i-3]+t[i] ←箱iを取った(その前に取ったのは3つ前)

とらなかった場合は単に直前までの最大値が伝播(でんぱん)されます。とった場合はその前に取ったところまでの最大値と箱iの価値を足します。

実は、3つ以上連続で取らないというのは考えなくてよいのです。なぜなら、3つ続けて取らないよりは真ん中のを取ったほうが得に決まっているからです。
それと、私は気づきませんでしたが、実はcase 3は考えなくてよいようです。というのは、「直前は3つ前」が最適解の場合、2つ前にその値が伝播されているはずだからです。(Thanks マサヤさん)

このプログラムは示しません。各自挑戦してみましょう。
下手をするとp[-1]などを参照してしまうので注意してください。




向き・不向き

最後に、動的計画法の向き不向きですが、これははっきり言って慣れるしかないと思います。

ザックリ言うならば、例えば、バックトラックのときのプログラムで、

backtrack(int x, int y, int k)
{
 if(k == n){
   ...
   return;
 }
 ...
 backtrack(..., ..., k+1);
 ...
}

このとき、nが大きいがx,yの取りうる範囲がそれほど大きくないとき、効果が大きいことが多いです。逆に、nが小さく、x,yの範囲がとてつもなく大きいときは、やめたほうが(バックトラックで解いた方が)いいでしょう。


バックトラック→動的計画法の書き換え

慣れてくると、バックトラック法から動的計画法へ機械的に書き換えることができる部分があることに気づくと思います。例えば、終了条件
 if(n == 0 || a == 1)
   return 1;
は、初期化の部分
 for(a = 0; a <= m; a++)
   p[0][a] = 1;
 for(n = 0; n <= m; n++)
   p[n][1] = 1;
に対応し、再帰呼び出し
 ret = part(n, a-1);
 if(n >= a)
   ret += part(n-a, a);
は、伝播の部分
     p[n][a] = p[n][a-1];
     if(n >= a)
       p[n][a] += p[n-a][a];
に対応しています。

なので、いきなり動的計画法で書くのが難しかったら、いったんバックトラック法のプログラムに起こしてみるのもいいかもしれませんね。