病みつきになる「動的計画法」、その深淵に迫る:最強最速アルゴリズマー養成講座(4/4 ページ)
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。
今回の問題の解法
今回の問題のポイントは、ヒントでも挙げた通り、「どうやって途中結果を保持し、無駄な計算をなくすか」です。これさえ気づけるようになれば、この手の問題の考え方は非常に簡単です。
今回の問題の場合は、「1行または1列ごとに、直前1行のパターンごとの最適な解を保持する」ことが分かれば解けたも同然です。ピンとこない方のために、図を用いて説明します。
上図のように、上の1行の情報だけ見える状態で、もう1行に情報を追加したとします。このとき、この1行を追加した際に増えた直線の本数は何本でしょう? こう聞かれた時に、この図さえ与えられれば簡単に答えられるでしょう。
ここで、1行を追加した際に増える本数を体系化すると、「その行において横棒が引かれた本数」と、「上の行と繋がっていない縦棒の本数」の和だと分かります。ここまで分かれば、「1つ上の行における、縦棒が引かれた場所」に対して、「そこまでの最小本数」を保持することで、動的計画法に落とし込めますね。
大筋の方針が立ったとしても、実装に悩むかもしれません。これは少し難しいのですが、コンピュータが2進数を使っていることを利用すると、シンプルに実装できます。2進数が判らない方は、0と1のみで整数を表現している、ということだけ分かれば十分ですが、よく分からない場合は検索するなどして少し調べてみてください。
上図のように線を引きたいとします。縦棒の場所さえ分かれば十分なので、縦棒がある場所を○、縦棒がない場所を×とすると、○××○××○×、と表現できます。この○を1に、×を0に変換すると、10010010となり、さらにこれを10進数に直すと146になります。たったこれだけで縦棒の有無を1行分、1つの整数で表わすことができます。縦棒のすべての組み合わせを調べたいのであれば、図のように横が8マスの場合、00000000から11111111までを調べればよいので、10進数にして0から2^8まで調べるだけで、簡単に全通りを求めることが可能です。
これは、縦棒を置きたい場所と、障害物があって置けない場所が被っていないかの判定にも役立ちます。コンピュータで2進法を取り扱う際は、ビット演算を覚えると、非常に処理が簡単にできますので、この際覚えてしまいましょう。以下の説明は、すべて2進数で表わした数字での説明です。
演算子 | 演算結果 | 例 | |
---|---|---|---|
and演算 | & | 両方のけたが1の場合は1に、そうでない場合は0になる | 10101 & 10011 → 10001 |
or演算 | | | どちらか片方のけたが1の場合は1に、そうでない場合は0になる | 10101 | 10011 → 10111 |
xor演算 | ^ | 両方のけたが同じであれば0に、そうでない場合は1になる | 10101 ^ 10011 → 00110 |
左ビットシフト | << | 指定された数だけけたを左にずらす | 00010010 << 2 → 01001000 |
右ビットシフト | >> | 指定された数だけけたを右にずらす | 00010010 >> 2 → 00000100(あふれた分は消滅) |
こんな演算どこで使うんだ、と思われるかもしれませんが、今回はこれが大活躍します。例えば、先程と同じように、障害物があるマスを1、そうでない場所を0として、その行の障害物の有無を表現した整数を作るとします。これと、次に置きたい縦棒の場所をand演算して、もし答えが0にならなければ、障害物と縦棒が重なっている、ということが分かります。
ほかにも、例えばaの7けた目が1かどうか知りたければ、if((a>>6)&1==1)のような条件文を書くことで簡単に判断できます。これを利用して、上1行の縦棒の場所を表わす変数prev、今回置きたい行の縦棒の場所を表わす変数now、今回置く行の障害物の情報field、列数nを用いて、追加しないといけない本数を表わす関数を作ると、以下のように簡単に書くことができます。
*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***
これができれば後は簡単です。上で書いた関数を使って、先程説明したようにソースコードに落とし込むだけで、簡単に答えが導けます。メモ化再帰を使ってももちろん解けますが、今回は動的計画法を用いた解法を示します。
計算量は、行数をn、列数をmとして、(直前の行のパターン数)×(次の行のパターン数)×(行数)×(列数)=2^n * 2^n * nとなるため、O(n*m*2^2n)となります。n=10、m=10のときで1億程度なので、内部の計算が少し重いですが、2秒以内なら十分処理できます。
*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***
さて、今回の問題はいかがだったでしょうか? 動的計画法を用いてさまざまな問題が解決できることや、動的計画法と2進数での状態の表わし方の相性の良さは分かっていただけたでしょうか。一見かなり実装が大変そうな問題でも、上手く実装すればこれだけシンプルになりますし、こうしたプログラミング上でのテクニックも徐々に覚えていくと、バグも少なく綺麗なソースコードが書けるようになります。
今回紹介したものよりも美しい実装方針を思いついたり、きれいなコードが書けたら、ぜひご意見いただければと思います。ソーシャルブックマークのコメントでも、筆者個人のブログに書き込んでいただいても構いません。可能な限り反応したいと思っていますので、どんどんご意見をお寄せください。
なお、今回からTwitter用の専用ハッシュタグも用意しました。今回の連載に関するTweetは「#SSAlgo08」をつけてつぶやいていただけばと思います。
それでは、次回もお楽しみに!
*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***
著者プロフィール:高橋直大(たかはし なおひろ)
Microsoftが主催する技術コンテスト「Imagine Cup」の2008年アルゴリズム部門で世界第3位に入賞した若きアルゴリズマー。TopCoderでは誰もが恐れるRedcoderとして活躍中。2009年に開催された「天下一プログラマーコンテスト」では特別賞を受賞した。現在、慶應義塾大学環境情報学部3年。口癖の「みょんみょん」が聞けるTopCoderニコ生オープン実況もじわじわと視聴者を増やしつつある。
世界でも有数のRedcoder、高橋直大がアルゴリズムの魅力と極意を伝授する「最強最速アルゴリズマー養成講座」はこちらから
関連記事
- アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった
動的計画法・メモ化再帰というと難しいアルゴリズムであるかのように聞こえますが、実際には小学生でも分かるほど簡単なアルゴリズムです。使用できるメモリと実行時間を意識しながら、同じ計算をする無駄を省くことができれば、かなりの実力者となれます。 - トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 - 知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 - 細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック
競技プログラミングはレベルの高い人たちの集まり――そんな考えを持っている初心者の方、TopCoderはあなたのコーディングスキルを爆発的に高める魔法のような場です。今回は、初心者にこそお勧めしたいTopCoderの魅力について考えます。 - 「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」
典型的なアルゴリズムをたくさん知っている人間が最強か――? いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。 - オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 - あなたの論理的思考とコーディング力は3倍高められる
全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。本稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。 - 高橋直大、Imagine Cupアルゴリズム部門で世界の三強に
- フランスの地でアルゴリズムの未来を切り開く男 高橋直大
Microsoftが主催する学生向けの技術コンテスト「Imagine Cup」。そのアルゴリズム部門で世界の頂点に挑むのは、プログラミング歴が2年にも満たない一人の数学好きだった。 - アルゴリズムと戯れる元野球少年が手に入れた宝物
Imagine Cup 2008のアルゴリズム部門で世界第3位となった高橋直大氏。彼の軌跡を眺めてみると、わたしたちが忘れてしまったことにすら気づかない何かを思い出させてくれるような気持ちになる。 - TopCoderで世界と渡り合う日本IBMの異才――夷藤勇人
もしあなたが美しい(あるいはトリッキーな)コードが飛び交う世界を知りたいと願うならそれはTopCoderに参加することで容易に実現することができる。このTopCoderに参加している数少ない日本人で、生涯プログラマーを宣言する人物にTopCoderの魅力を聞いた。
関連リンク
Copyright © ITmedia, Inc. All Rights Reserved.