Visualizing Memoization and Dynamic Programming(2)

前回のエントリでは、3003 -- Spiderman’s workoutの解法としてメモ化再帰を解説しました。今回のエントリではこれを元に、動的計画法を解説します。


まず、前回のエントリにて実装したsearch関数を見てみましょう。

#define INT_INF 999999

int memo[40+1][1000+1];

int search(int i, int j)
{
  if (memo[i][j] >= 0)
    return memo[i][j];

  if (i == M)
    return memo[i][j] = (j == 0) ? j : INT_INF;

  if (j - d[i] >= 0) {
    return memo[i][j] = std::max(std::min(search(i + 1, j - d[i]),
                                          search(i + 1, j + d[i])),
                                 j);
  }
  else {
    return memo[i][j] = std::max(search(i + 1, j + d[i]), j);
  }
}

memset((void*)memo, -1, sizeof(memo));

search(0, 0);

search関数はメモ化再帰としての実装です。関数本体からsearch(0, 0)を呼び出すことにより訪れた節点を計算し、記憶領域に記録してくれるのでした。

一度訪れた節点は再度計算しません。メモ化再帰が計算量を劇的に減らしたのはそのためでした。これは任意の節点を根とする部分木がそれぞれ独立した問題である事実によって成り立っています。

例えば、(3, 6)を根とする部分木は以下となります。

元々の問題は「高さ0から始まり、与えられた高さを昇り降りした結果、高さが0になる経路」を探索する問題でした。これは(0, 0)を根とする木に該当します。同様に、(3, 6)を根とする部分木は「高さ6から始まり、与えられた高さを昇り降りした結果、高さが0になる経路」を探索する独立した問題と考えることが出来るのです。

そのため、(3, 6)を根とする部分木を計算するために、どのように(3, 6)に到達して来たかを知る必要はありません。この問題の場合、部分木は独立して計算出来るのです。これはとても重要なことなので、分からなくなってしまったら思い出すようにしてください。

では、実際に(3, 6)を計算するにはどうしたらよいでしょう? (3, 6)は(4, 3)と(4, 9)の部分木の計算結果を必要とします。具体的には、(4, 3)と(4, 9)の計算結果のより小さなものと現在の高さを比べ、より大きい値を結果とするのでした。数式として表すと以下となります。

さて、部分木はそれぞれ独立して計算出来るのでした。(3, 6)の計算には(4, 3)と(4, 9)の計算結果が必要ですが、(4, 3)と(4, 9)は(3, 6)のことを気にする必要がありません。数式にすると以下となります。確かに、深さが3のものについては考えなくてよいようです。

さらに続けてみましょう。

数式にf(6, *)が現れました。f(6, *)は末端、つまり葉の節点であり、これ以上昇り降りをする必要がありません。そのため、その高さから結果を計算することが出来ます。繰り返しになりますが、(6, *)を根とする部分木も独立して計算することが出来るのです。

数式を一般化してみましょう。

メモ化再帰関数として実装したsearchは、この式を解くものだったのです。それぞれの節点での計算は、子の節点群の計算結果を元に計算します。結局、search関数は木の末端、葉から根に向けて計算し、結果を伝搬していたのです。

さて、末端の節点の計算式をもう一度見てみましょう。式は一般化したものです。

末端の節点、深さがMの節点は他の節点に依存せずに計算出来ることがわかります。

ここで式を変更しておきましょう。メモ化再帰を考えていた際は再帰関数であることを表すために関数の形を取っていました。ここからは、記憶領域に直接保存するようにします。

ここまでを実装してみましょう。

  int dp[40+1][100+1];

  int jp = std::accumulate(d, d + M, 0);

  for (int j = 0; j <= jp; j ++)
    dp[M][j] = (j == 0) ? 0 : INT_INF;

結果は以下のように格納されます。

では次に深さM-1について考えてみましょう。この深さでは二つ目の式を使うのでした。ここに、M-1を代入してみましょう。

これまでに見てきたように、深さM-1の節点の計算を行うにはもう一段深い、深さMの節点の計算結果を用いることが分かります。これも実装してみましょう。

  for (int j = 0; j <= jp; j ++) {
    int l = (j - d[M - 1] >= 0 ) ? dp[M][j - d[i]] : INT_INF;
    int r = (j + d[M - 1] <= jp) ? dp[M][j + d[i]] : INT_INF;

    dp[M - 1][j] = std::max(j, std::min(l, r));
  }

深さM-1の節点も計算し、記憶領域に保存してみましょう。

深さM-2についても同様の計算を行い、記憶領域に格納します。

これを深さ0まで続けると、記憶領域は以下のようになります。

これを反映した実装は以下となります。深さがMの場合の実装と深さがMより小さい場合の実装を反復とし、繋げたものです。

  int dp[40+1][100+1];

  int jp = std::accumulate(d, d + M, 0);

  for (int j = 0; j <= jp; j ++)
    dp[M][j] = (j == 0) ? 0 : INT_INF;
  
  for (int i = M - 1; i >= 0; i --)
    for (int j = 0; j <= jp; j ++) {
      int l = (j - d[i] >= 0 ) ? dp[i+1][j - d[i]] : INT_INF;
      int r = (j + d[i] <= jp) ? dp[i+1][j + d[i]] : INT_INF;

      dp[i][j] = std::max(j, std::min(l, r));
    }

では元々の問題をもう一度考えてみましょう。元々の問題は「高さ0から始まり、与えられた高さを昇り降りした結果、高さが0になる経路」を探索する問題だったのでした。これを強調して視覚化してみます。

単純な反復による計算によって、メモ化再帰を用いた実装と同じ結果が得られたことがわかります。この技法が動的計画法と呼ばれるものです。動的計画法は細かな技法部分の解説こそなされていますが、本質を言い当てた文章を見ることがほとんどないように思います。しかし、名著アルゴリズム Cでは見事にそれを言い当てています(第3巻 42章)。

これまでに学んだアルゴリズムの設計の際に、大きな問題を分割して独立に解けるような小さな部分問題に分けるという分割統治(divide and conquer)の原理が使われることがしばしばあった。動的計画法(dynamic programming)は、この原理を極限まで用いる方法である。すなわち、最終的な解をえるために小さな問題のどれを解くべきかが正確にはわからない時、単純にそれらをすべて解いてその答えを記憶しておき、それらを使ってもとの大きな問題を解く。

まとめ

今回のエントリでは前回解説したメモ化再帰による実装を元に、動的計画法による解法を解説しました。

メモ化再帰動的計画法プログラミングコンテストで多用する技法です。プログラミングコンテストというと技法や技巧を無理に使わせるように問題を用意していそうだし、実際に役に立つか疑問である、という方もいらっしゃるかと思います。

しかし、メモ化再帰動的計画法を必要とする多くの問題は身近な問題を題材としているように感じます。身近に思えるだけに、効率的に実装出来ず悔しい思いをしたことがあった問題が解けるようになるのです。これがプログラミングコンテストを解きすすめることによって自然に身に付いてしまう。その気になれば、動的計画法に関する問題だけを検索し、集中的に挑戦することすら可能です。これをやらない理由がありません。

また、これらの技法は効率的なだけではなく実装が大変楽しい技法でもあります。そのような問題を見つけたらまた紹介して行きたいと思っています。

アルゴリズムC〈第3巻〉グラフ・数理・トピックス

アルゴリズムC〈第3巻〉グラフ・数理・トピックス

プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブック