Visualizing Memoization and Dynamic Programming(1)

昨年のSIGGRAPH参加後、9月ほどからでしょうか。アルゴリズムに関する知識と実装する力を基礎から鍛え直す衝動にかられ、北京大学Judge Online(以下POJ)に参加するようになりました。現在のAC数は123問とまだ少ないですが、一つ一つの問題を解くごとに発見があり、驚きがあります。

さて今回のエントリではPOJの問題の中から3003 -- Spiderman’s workoutを紹介したいと思います。考える過程が大変面白かった問題です。今回のエントリではメモ化を用いた解法を解説します。次回のエントリにて動的計画法を用いた解法を解説する予定です。

以下、問題の超訳です。

スパイダーマンは体型を保つために、毎日の運動を欠かしません。地面、つまり高さ0メートルから運動を始め、予め与えられたm回の高さを昇り降りします。昇るか降りるかは選ぶことが出来ます。ただし、スパイダーマンは運動が終わったときに地面に戻って来たいと考えています。

スパイダーマンのために運動の計画を立ててください。条件は以下とします。

- m個の数値は(d_1, d_2, ..., d_m)として与えられます。最大で40個までとします
- スパイダーマンは地上より低い高さには行けません
- どのような組み合わせで昇り降りを行っても、1000メートルを超えることはありません
- 運動の計画は、"U"と"D"で表してください。例えば、"UDUD"は昇り、降り、昇り、降りを表します
- スパイダーマンは高いところが苦手なので、複数の組み合わせが考えられる場合は到達する高さが一番低い組み合わせを選んでください
- どのような組み合わせでも地面に戻って来れない場合は、"IMPOSSIBLE"と出力してください

例:

3 2 5 3 1 2

解:

UUDUDD

3003 -- Spiderman’s workout

問題では最適な経路の出力を求めていますが、まず高さ0から始まり、全ての分岐を経た後に0に戻る経路の存在を調べる関数を実装します。

bool search(int i, int j)
{
  if (i == M)
    return j == 0;

  return search(i + 1, j - d[i]) || search(i + 1, j + d[i]);
}

search(0, 0);

これは全探索による実装です。つまり、各接点にて数値d_iを足すか引くかで分岐を行う方法です。探索木は以下のようなものになります。

全探索の組み合わせ数は2^mです。ここでは6回の分岐を行っています。経路の数は64通りです。

O(2^n)のアルゴリズムは大きなnについて解くのが難しいことで知られています。問題の条件にある最大40回の分岐を行うと、その組み合わせ数は1099511627776通りとなります。これでは厳しい時間制限のあるPOJに投稿することはおろか、自端末でのテストすら終了しません。

さて、図の左側を拡大してみます。検索木に高さが負となる接点が多量に含まれていることが分かります。これらの接点は問題の条件に反するため、有効な経路として成立しません。そのため、それ以降の部分木を探索する必要もありません。

では、有効な部分木を抽出してみましょう。

探索すべき経路を随分絞り込むことが出来ました。このように無駄な探索を打ち切る技法を枝刈りと言います。この技法を反映した実装は以下となります。

bool search(int i, int j)
{
  if (i == M)
    return j == 0;

  if (j - d[i] >= 0) {
    return search(i + 1, j - d[i]) || search(i + 1, j + d[i]);
  }
  else {
    return                            search(i + 1, j + d[i]);
  }
}

search(0, 0);

枝刈りを行った探索木の接点の配置を変更してみましょう。探索木のレイアウトにはConsistent Binary Tree Layout(1)で紹介した技法を用いています。接点の深さを垂直方向の位置に、また接点の通りがけ順の順序を水平方向の位置とする技法です。

探索木全体の見通しが大変良くなりました。空間にも余裕が出来たため、分岐の様子も接点間に設けます。

では、問題の条件を満たす経路について考えてみましょう。高さ0から始まり、全ての分岐を経た後に0に戻る経路を探します。この条件を満たす経路は2つ存在することが分かります。

条件を満たす経路が複数存在する場合、到達する高さがより低い経路が解となります。条件を満たす2つの経路はそれぞれ最大の値が6である経路と5である経路です。そのため、求める解は高さが0、3、5、0、3、2、0と推移する経路であることが分かります。

さて、枝刈りを行うことで探索すべき経路の数をかなり絞り込むことが出来ました。しかし、この問題を解くには枝刈りのみでは不十分です。枝刈りを行っても経路の数がたった半分にしか減らない場合があるからです(500 1 1 1 1...という例を考えてみましょう)。

枝刈りを行った探索木をさらに観察してみましょう。同じ部分木が何度か現れていることが分かります。

同じ部分木について計算を行うのは明らかに無駄ですので、再計算しないように工夫してみましょう。まず、大きめの部分木を再計算しないような経路を考えてみます。

いいですね! さらにこの考え方を末端の接点まで適用してみましょう。再計算する必要のない接点がさらに増えるはずです。

...ちょっと待ってください。どうも気持ちが悪い。

この図は直感的でしょうか? 見ていると余計に混乱しそうです。書店でこのような図を掲載している書籍を見つけたら買って帰りたいと思うでしょうか。私は購入しないと思います。問題をより複雑にしているようにしか思えません。一体何がよくなかったのでしょうか?

原因は接点の配置方法にあります。接点の垂直方向の位置は分岐の深さという意味のある値を表していますが、水平方向の位置には特に意味合いを込めていませんでした。接点の水平方向の位置に通りがけ順の順序を用いる技法はバランスの取れた二分木のレイアウトを行うのに大変有用です。しかし、この問題の探索木を考える上で適切なものではなかったのです。

では、水平方向の位置の意味合いを変えて再度考察してみましょう。今回は接点を訪れた際の高さを用います。

明らかに整理された、美しい探索木となりました。それぞれの深さで重複した接点が現れることがないので、同じ処理を無駄に繰り返す部分木も消えてなくなってしまいました。

それでは、この探索木を元に再計算を防ぐ方法を考えてみましょう。これはそれほど難解なことではありません。一度計算した結果を後で再利用するために記憶しておけばよいのです。では、結果をどのように記憶させればよいでしょうか。先ほどの図を元に考えると、以下のように多次元配列を記憶領域として用意すればよいことは明らかです。多次元配列のそれぞれの要素には、接点の深さと高さを母数としてアクセス出来ることが分かります。

上の図に経路を重ねてみましょう。この構造が計算結果を記憶するのに大変適したものであることが分かります。

さて、各接点では何を計算し記憶させればよいでしょうか? 一先ず、以下としてみましょう。

  • 接点が末端である場合は、その高さを返す
  • そうでない場合は、
    • 子の接点の高さのより小さいものと、
    • 自分自身の高さを比べ、より大きいものを返す

この条件で計算を行った結果、記憶領域は以下のようになります。

実装に反映すると、以下となります。

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;

  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);

このように計算結果を記憶する技法のことをメモ化(Memoization)と呼びます。また、メモ化を伴った再帰のことをメモ化再帰と呼びます。

計算が終了した後に記憶領域を深さ0、高さ0から再び追跡すれば、問題の解となる最適な経路を得ることが出来ます。経路が別れる場合は、計算結果がより小さいものを経由するように経路を選択します。

しかし、実はこれだけではなお不十分です。数値を一つ減らした例を考えてみましょう。

この例では高さ0から開始し、高さ0に戻る経路が存在しません。しかし計算結果を追跡し終わるまでそれを判別することが出来ません。計算方法を少し変更してみましょう。

  • 接点が末端である場合で、
    • 高さが0である場合は、0を返す
    • そうでない場合は、有効な経路ではないことを示す大きな値を返す(INT_INF - 999999とします)
  • そうでない場合は、
    • 子の接点の高さのより小さいものと、
    • 自分自身の高さを比べ、より大きいものを返す

この条件で計算を行った結果、記憶領域は以下のようになります(INT_INFを*として表しています)。最適な経路の復元を確実に行うことの出来る結果となりました。

実装に反映すると、以下となります。

#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);

数値を一つ減らした例では以下のような結果となります。計算が終了した後に高さ0、深さ0の要素にアクセスすることで、有効な経路が存在しないことが判別出来るようになりました。


まとめ

今回のエントリでは、POJ3003 -- Spiderman’s workoutを元に、メモ化再帰の解説を行いました。全探索ではO(2^n)だった計算量が、メモ化を行うことで最悪の場合でもO(n x m)に減らすことが出来ました。最悪で1099511627776の計算量が最悪でも40000(40 x 1000)になったことになります。メモ化を伴うことで、大きなnに対応しうる実装となった、ということです。

次回のエントリでは今回紹介したメモ化に続き、動的計画法を用いた解法を解説する予定です。

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

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

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

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