はじめに
【その0】,【その壱】で主に理論周りについて学びました。特に【その壱】ではプログラム的に処理するまでご紹介しました。【その弐】ではコーディング面についてご紹介します。
【その壱】で簡単に紹介した枝狩り法を実際にプログラミングするとき、「理屈は理解したが、どのようにコードを書けば良いのかが分からない」などの疑問が生じると思います。
また、ナップサック問題に対する枝狩り法はパターンを覚えたので実装できるが、業務で求められる問題パターンを枝狩り法で処理したいが、どのように実装して良いかが分からないといった応用の仕方が分からないという問題が生じることもあると思います。
筆者もアルゴリズム初学の頃は多くの実装に関する問題に悩まされたので、その経験を元に解決方法をご紹介します。
なぜ実装できないのか
※「動的計画法」というアルゴリズムを聞いたことがない読者はこの節を読み飛ばしても問題ないです。
実装できない理由は固定観念に囚われすぎている点にあると思います。
アルゴリズムを勉強し始めの頃や競技プログラミングをやり始めた頃に「動的計画法」というアルゴリズムを目にすると思います。この「動的計画法」はアルゴリズムの登竜門であり、競技プログラミングでは頻繁に使われるものです。
動的計画法は言葉で理解するには簡単ですが、いざ実装しようとするとどうしていいか分からなくなる方が多いと思います。これは動的計画法で扱う配列構造のイメージと木構造のイメージが互いに正しく結びついていないことが原因かもしれません。実装できない方の多くは下図のようなイメージがあると思います。
「配列を用意して、”左から右へ順”に処理していき、最後に辿り着いた一番右側に答えが出てくる」このようにイメージされていると思います。同様に２次元配列でも「配列を用意して、”左上から右下へ順”に処理していき、最後に辿り着いた一番右側の列に答えが出てくる」。
これを木構造で表現すると大体は下図のような処理順になることが多いと思います。
ここで実装の障害となるのは”木の探索順は１パターン”ということです。
動的計画法までアルゴリズムの学習を進めた方なら一度は「深さ優先探索」「幅優先探索」といった様々な探索方法を勉強したと思います。木の探索の仕方は様々なパターンがありますが、動的計画法が絡んだ瞬間に固定観念によって、木の探索が”上から下”への１パターンになる現象が起こります。
この一例のように”理屈は理解したが、実装になると上手くいかなくなる”現象を解決する手法を次にご紹介します。
情報を整理する
【その壱】で紹介した「ナップサック問題」を例に解決手法をご紹介します。
先に結論から
計算機的関数Fの入力に求めたい情報を入力として扱ってよい。
これは疑似コードで表現すると下記のようになります。
Function(各物の「持ち帰る」と「持ち帰らない」、選んだものの総価値) {
IF 選んだものの総容量 < バッグの容量
Return 選んだものの総容量
}
このような関数表現ができるということです。これによって実装パターンを複数用意できます。なぜこのようなことが出来るのか、そのプロセスを以下にまとめます。
情報の流れとは”入力と出力”であるため、まずは入力と出力を整理します。
入力：各物の「持ち帰る」と「持ち帰らない」、各物の重さ、各物の価値、バッグの容量 出力：選んだものの総価値
このように整理できると思います。この情報を元に数学的に関数表現をすると
関数F(入力) = 出力 = 選んだものの総価値
このように表現できます。これが”なぜ実装できないのか”の節であげた木構造の探索順の１パターンになります。計算機的表現では数学的関数表現に加えて副作用を用いた表現があります。いわゆるグローバル変数などです。副作用を用いることで関数の入力を出力のように扱うことができます。つまり下記のような表現もすることができます。
計算機的関数F(各物の「持ち帰る」と「持ち帰らない」、各物の重さ、各物の価値、選んだものの総価値) = 選んだものの総容量 < バッグの容量
本来出力である情報が関数の入力として扱うことが出来ます。これで枝狩り法を実装すると”木構造の探索順序”が変わります。さらに計算機的定数表現を用いることで条件によっては情報の桁落ちを実現できます。この例だと各物の重さと各物の価値を定数表現できます。つまり下記のようにシンプルな計算機的関数を定義できます。
計算機的関数F(各物の「持ち帰る」と「持ち帰らない」、選んだものの総価値) = 選んだものの総容量 < バッグの容量
このように関数を柔軟に考えることでアルゴリズムの実装（特に組み合わせ系）が比較的簡単になると思います。
応用する
重要なポイントは情報の整理にあります。先ほどのように情報を整理して、関数の定義を見直すことで木構造の探索順序を変更することができました。この事実を応用することで動的計画法の実装を理解することが出来ます。
ナップサック問題の動的計画法は2次元配列を用いることが多いと思います。その時は下記のような定義をすると思います。
DP[i][j] = 選んだものの総価値
このi, jは現在参照している”ただの行と列”を表すとイメージしている方が多いと思います。そのイメージは正しく、実際に行と列を表すものです。ただし、動的計画法を上手く実装できる方はこのイメージに加え、次のようにイメージします。
DP[もの][各物の「持ち帰る」と「持ち帰らない」] = 選んだものの総価値
このようにi, jは情報としてイメージします。これを関数表現でやったことを応用して
DP[情報][情報] = 情報
として定義します。そして実装しやすいように情報の中身を定義し、実装します。これは”情報を整理する”でまとめたように”木構造の探索順序”が変わるだけです。また、このように整理することで更に応用が効きます。
例えば、最短経路問題で地点Aから地点Dへの移動問題を解くときにダイクストラ法を用いたりなどで答えを出したりするのですが、ここに地点Cから地点B間に制約が入ったりなどで一般的に定義されているダイクストラ法の形だけで理解していると、途端に実装できなくなります。ですが、同じように情報を整理することで解けるようになります。2次元配列で定義していたが、制約という情報が入ったので3次元配列に拡張してあげるなどです。
まとめ
本記事では下記の項目をご紹介しました。
・情報の整理
・情報整理の応用方法
【その弐】では、【その壱】で足りなかった実際に実装する時のコーディングテクニックをご紹介しました。
ビジネスの世界で扱うプログラミングは「車輪の再開発」などといったスローガンがあるように効率面に重きを置いているため、ビジネス要件もそれに沿うように調整することが多く、１パターンでの実装で上手くいくことが多いですが、情報の整理はバグを回避するなどの使い方もあるため、複数のパターンでの実装方法を考え、見比べることをオススメします。
