年の瀬 / 動的計画法

7 時起床。ちょっともたついていたら珈琲をいれる時間もなく、 身支度をしてすぐに出勤。 満員電車と満員バスに乗ってキャンパス着。 9 時から卒研ゼミＩ。 ポワソン分布による近似、誕生日問題再び。 そのあとは雑用をあれこれしてから、 早めの昼食。 12:30 から卒研ゼミＳ。Orlicz 空間について。 続いて、14:10 から「プログラミング演習」。 素数定理の数値計算を課題に出した。 部屋に帰ると事務の方が来ていてちょっと対応したり、 あれこれのあと、雨の中を帰る。 電車の中で、おばさんが雑誌のおせち料理のレシピを熟読していた。 一方、おじさんが読んでいるスポーツ新聞は紅白歌合戦の記事だ。 もう年末だなあ。

近所のスーパーで食材を買って帰宅。 明日は朝から夕方まで休みなしの水曜日なので、 せめて美味しいサンドウィッチでも作って持って行こうと思い、 サンドウィッチ用の食材も調達。 夕食はチゲ鍋。ボルドーの赤を一杯だけ。あとは雑炊。 食後に珈琲を一杯。 夜は趣味のプログラミングをしたり、 明日のサンドウィッチの具を仕込んだり。

時に、なるほど、と膝を打つようなアルゴリズムがある。 例えば、でたらめに並んだ数を大きい順に並びかえる高速アルゴリズムの、 「クイックソート」などだ。 私が自分で気付いて、とても嬉しかったアルゴリズムの一つに「動的計画法」 と呼ばれるものがある。 色々な数が一段目に一つ、二段目に二つ、三段目に三つ、 と言う具合に三角形に並べられているとせよ。 この数を一番上から、右下か左下を選んで下へ下へと段を下りながら、 その数を足し合わせていく。 このとき、一番その和が大きくなる通り道を探せ。 素朴に考えると、一段下がる度に右か左か二通りの選択があるので、 N 段の三角形に対し、2 の N 乗の通り道の可能性がある。 これを全部調べるとすると大変巨大な計算量になる。 しかし、これには非常にうまい高速計算法がある。 上からではなくて、下の段から計算するのだ。 あることに気付くと、計算量が二倍ではなくて半々になっていき、 全体で N の二乗程度の計算量になる。 動的計画法の典型例である。 昔、初めて自分でこの原理に思い当たったときは嬉しかった。 しかし、今になって悟ったことには、 この原理自体はこのような骨組だけの問題を出されれば、 少し考えれば誰でも思いつくのだ。 大事なのは、そして難しいのは、 一般の問題からこの骨組を抽出すること、 逆に言えば、 一般の問題をこの動的計画法の問題に帰着することである。