アルゴリズムマスターへの道　～【その壱】アルゴリズムを業務で活かすためのプロセス～

はじめに

【その0】でアルゴリズムを学ぶための道具を学びました。
【その壱】では実際に問題を解くアルゴリズム採用プロセスをご紹介します。
【その0】,【その壱】は【その弐】以降の記事を読むための知識・基礎編となります。

クラスPとクラスNP

【その0】で「優しい問題」と「難しい問題」をご紹介しましたが、【その壱】では更に細かく問題を分類する概念をご紹介します。問題を分類することは数多のアルゴリズムを絞り、その問題に対しての適切なアルゴリズムの選択の手助けになります。今からご紹介するのは「クラス\(P\)とクラス\(NP\)」という概念です。
普段からプログラミングをしている読者の方は「遺伝的アルゴリズム」というアルゴリズムを一度でも聞いたことがあるという方は多いかと思います。この「遺伝的アルゴリズム」はクラス\(NP\)に対しての有効的なヒューリスティックなアルゴリズムです。

さて、まずは難しい定義からご紹介します。

クラスPとは「多項式時間で解ける問題の集合」、一方のクラスNPは「問題の解が正しいかの検証は多項式時間で可能だが、多項式時間で解を見つける方法は知られていない問題の集合」です。

我々プログラマ目線で「多項式時間」は現実的に解ける問題と認識すれば十分でしょう。この認識であれば、クラス\(P\)に所属する問題は現実的に解けるアルゴリズムが存在し、その中で更に高速に解けるアルゴリズムを探すのが我々プログラマとしての選択になると思います。
クラス\(NP\)は

非決定性チューリングマシンを用いれば多項式時間で求まる問題の集合

とまた別の定義もあります。
「非決定性チューリングマシン」とは、if-else文があったとき必ずどちらか１つのロジックを走るのが普通の計算機に対して、両方のロジックを走らせることのできる計算機となります。そのため現実的に使用しているPCに非決定性チューリングマシンは存在しないです。なので裏を返せば現実的に解ける問題ではないのかもしれないとイメージするのが良いでしょう。

更に問題を細かく分類するNP完全やNP困難などがありますが、業務をする上でそこまで詳しく追及されるようなことはあまりないと思いますので、本記事では割愛しますが、興味があり更に深く知りたい方は是非調べてみてください。

ナップサック問題

計算の複雑性すなわち計算の難しさを話題にあげると高確率で話題に挙げられる有名な問題を１つご紹介します。

りんご25g、みかん10g、いちご7g、すいか1000g、とまと20g、めろん12g
とこのお店では、果物とその重さが決まっています。気前の良い店主は日ごろの挨拶のお礼にと、それぞれ1個ずつだけ持って帰っても良いとあなたに言ってくれました。ところであなたのバックは合計30gまでしか入らないです。そのため30gに収まりつつ、一番価値が高くなるように持ち帰ろうと決めました。一番価値が高くなる果物の組み合わせの合計の価値を計算し、出力するプログラムを考えてみてください。
ただし、価値はそれぞれ、100、40、20、10000、90、50となります。

このような形の問題をナップサック問題と呼ばれ、クラス\(NP\)に所属すると知られています。
※この問題は整数計画問題に所属し、整数計画表を用いて数学的な表現が出来るのですが、高校数学レベルで理解するには少し難しいと思いますので本記事では割愛します。

さて、この問題を用いてアルゴリズムを業務へ生かすプロセスを考察していきたいのですが、いきなり何のアルゴリズムを選択すれば良いか考えるのは、かなりの経験を積んでない限りは良くない手法です。まずは小さい問題に置き換えて、この問題の性質を掴むのが良いと筆者は思っています。
そこでまずはりんごとみかんだけで考えてみましょう。すると組み合わせが4組み出来ると思います。

りんご	みかん	重さ	価値
持ち帰る	持ち帰る	35g(重量オーバー)	140
持ち帰る	持ち帰らない	25g	100
持ち帰らない	持ち帰る	10g	40
持ち帰らない	持ち帰らない	0g	0

問題をプログラミングで解決する

さきほどまでは問題を数学的に分析しました。そこで次にすることは理論から実践に落とすプロセスです。
分析結果から”全部の組み合わせを処理”すなわち全探索で問題ないと結論が出ましたが、ここでは\(N\)=100000などの大きい計算量の場合で考えてみましょう。その場合は全探索をするととんでもない時間がかかり、サービス的にボトルネックになる可能性が出てきます。
この状況下で理論を実践に落とすプロセスですが、残念ながら情報工学という学問に対するビッグデータ(経験値)に依存しやすいです。筆者の思考プロセスのパターンをいくつか上げると、整数計画問題に落としそのまま整数計画問題として解けるか確認、整数計画問題を線形緩和してシンプレックス法で解けるか確認、遺伝的アルゴリズムや動的計画法や枝刈り法が役に立ちそうなので試してみるかなど、自信のビックデータに基づいて理論を実践に落とす必要があり、なかなか難しい課題になりがちです。
問題を数学的に分析する過程は社会人になるまでに学習した数学というビックデータ(学問)でアプローチできることが多いため、多くの方はさほど苦戦することなくある程度の理解は出来たと思います。
同じように理論を実践に落とす技術に関するビックデータを溜めていく必要があります。このビックデータを提供することを目的にしているのが”アルゴリズムマスターへの道”というシリーズになります。
理論を実践に落とす方法を学ぶ一番の近道は”アルゴリズムの性質”を理解することだと筆者は考えています。そこを重点に置き、この問題を解くアルゴリズムをご紹介します。

枝刈り法

理論を実践に落とす技として比較的分かりやすい枝刈り法というアルゴリズムがあります。
これは多くの組み合わせ系問題に有効的です。
このアルゴリズムの本質は”早い段階で必要のない計算は打ち切る制約を加える”点です。
例えば、りんごとみかんをどちらも持ち帰る時点で35gと容量オーバーで他の果物を持ち帰るか持ち帰らないかは重要ではなくなります。なので容量を超えた時点でその組み合わせの処理は打ち切りにすることで計算量を減らすことが出来ます。
また、このアルゴリズムによる処理は木構造を用いて絵として表現できます。

どこかで実装に失敗し、期待通りの結果を得ることに失敗しても絵を描いてイラスト的にデバッグすることも可能です。
木構造の1辺を枝として表現し、制約による処理を打ち切る動作を”枝を切る”という表現をすることで枝刈り法という名前にピンとくると思います。
このアルゴリズムを採用するかの評価の仕方は、どれだけ強い制約を加えられるかになります。今回は容量という制約を加えることで多くの枝を刈れそうですが、もし次の制約しか加えられなかったらどうなるでしょう。

容量が1073gを超えてはいけない

この制約しか加えられない時、刈れる枝は全ての果物を持ち帰るパターンのたった１つの枝のみです。つまり計算量的には、ほぼ変わることはなく全探索しているのと同じになります。
これは大げさな例ですが、難しい問題になると計算量が全く削れないことが起きたりします。
従って、どれだけ強い制約を加えられるかを評価するのが良いと思います。
さて、ここまでの内容は理論から実践に落とすための手法の選択です。次に理論から実践に落とすための実装手法を学ぶ必要があります。

枝刈り法をプログラム的に処理する

このアルゴリズムの実装には様々な方法があります。
一例をあげると

・木構造を形作るデータ構造を作り、最大価値を探索する
・for文で回し、結果を配列に入れる(漸化式)
・再帰関数

などがあると思います。この中からこの手法を取るべきというのはないです。
チーム開発をしているので再帰関数で実装するとメンバーに負担をかけるので慣れ親しんでいるfor文で処理するなど、環境に応じて実装すれば良いと考えます。
もし、アルゴリズムを学ぶための目的であれば、筆者は再帰関数での実装をオススメします。その理由は筆者の経験談によるものですが、アルゴリズムの勉強で参考にした書籍などは比較的再帰関数での実装が多かったように感じたからです。また、再帰関数での実装に慣れておけば、そのうち動的計画法やメモ化再帰などのアルゴリズムに触れた時、実装での考えが助けになってくれると思います。

まとめ

本記事では下記の項目をご紹介しました。

・クラスNPに所属する問題
・問題を数学的に分析する手法
・理論から実践に落とすための手法

【その壱】までは初心者向けに基礎のご紹介となりましたが、【その弐】からは基礎を離れ、実際のビジネスで扱うアルゴリズムなどをご紹介することを考えています。その時に必要な基礎知識があれば随時補うとして、基本は理論から実践までをご紹介しようと思っています。