POH Lite の深さ優先探索アルゴリズムの計算時間
Paiza オンラインハッカソン Lite の開催が終了して、公式ブログに模範回答などが掲載されていました。掲載されているアルゴリズムは、(1) 最小金額を深さ優先探索で求めるもの、(2) 動的計画法を利用するもの、(3) 削減可能金額を最大化する問題に置き換えて動的計画法を利用するもの、三通りに分けられるようです。以前の記事で紹介した私の解き方は (2) に分類されます。
【結果発表】炎上中の20万人月PJを鎮火させた14言語のコード - paiza開発日誌
これらの中で (1) の深さ優先探索による解法がとても興味深かったので、自分でも実装して、動的計画法に基づく実装と比較してみました。実装したプログラムは以下にあります。
pohlite-data-generator/solve_depthfirst.cpp at 1.0 · y-uti/pohlite-data-generator · GitHub
深さ優先探索で解くプログラムは、公式ブログに掲載されたものとは別に、下記のウェブページでハッカソンの開催期間中から公開されていました。私が今回実装したプログラムは、こちらの実装を参考に C++ で書き直したものです*1。元プログラムに対する改良として、least_cost の計算で最後まで break しなかった場合も枝刈りの対象としました。これは、残りの下請け会社すべてに発注しても必要人数に到達しない場合になります。
paiza オンラインハッカソン lite(https://paiza.jp/poh/kirishima) pythonによるコード #paizahack_lite
まず、それぞれのアルゴリズムで問題を解いた場合の計算時間を比較します。次に示すグラフは、下請け会社数 (以下、N と表記します) ごとの計算時間をプロットしたものです。入力データは、以前の記事で紹介したサンプルデータの data_un_*.txt (下請け会社の人員数を 1 から 10,000 の一様分布、単価を平均 100, 標準偏差 10 の正規分布としてサンプリングしたもの) を用いました。必要人員数は、N * 5,000 / 2 としています*2。左のグラフが動的計画法で解いたもの、右が深さ優先探索で解いたものです。左右のグラフで各軸の大きさが異なっていることに注意してください。動的計画法による実装では、N = 10,000 で 350 秒弱の時間がかかっていますが、深さ優先探索では N = 50,000 でも 2.5 秒弱と、深さ優先探索の方が圧倒的に速く計算できています。なお、動的計画法の方は計算に時間がかかりすぎるため、N = 10,000 までの問題しか解いていません。
深さ優先探索のグラフは、きれいな単調増加にならず、でこぼこになっています。これは、深さ優先探索のプログラムの最悪計算量が O(2^N) で (記事末尾の追記を参照)、入力データによって枝刈りの効果が大きく異なってくるためだと考えられます。最悪のケースが発生する具体例として以下の入力データを考えてみます。
5 5 1 1 1 1 1 1 1 1 10000 1000000
このデータは、必要人員数 5 に対して、人員数 1、発注金額 1 の下請け会社が 4 社、人員数 10,000、発注金額 1,000,000 の下請け会社が 1 社というものです。必要人員数を満たすためには最後の下請け会社に発注するしかありませんので、この問題の解答は 1,000,000 になります。深さ優先探索でこの問題を解く過程を考えると、枝刈りが一切機能せず、二分木のすべてのノードを辿ることが分かります。入力データの必要人員数と下請け会社を 1 増やすごとに木のノード数は倍々に増えていき、それに比例して計算時間も大きくなっていきます。
さて、以上のことから、深さ優先探索による解法は、最悪計算量は O(2^N) ですが大抵の場合は高速に計算できるということが分かってきました。すると今度は、最悪に近いケースがどのくらい頻繁に起きるのか、という疑問が生じます。平均計算量を考えることがこの疑問に対する一つの答えになるのだろうと思いますが、今回の問題で平均計算量を求めるのはとても難しそうなので、入力データを大量に作成して、計算時間の分布を見てみることにします。
次のグラフは、N を固定して作成した 1,000 とおりのデータについて、計算時間のヒストグラムを作成したものです。左のグラフは、動的計画法による実装で N = 1,000 としたもの、右は深さ優先探索で N = 10,000 としたものです。横軸は計算時間、縦軸はその時間で計算が終了した回数です。ヒストグラムの刻み幅は 0.01 秒としました。たとえば 0.105 のところは、計算時間が 0.1 秒以上 0.11 秒未満で終了した回数を表します。深さ優先探索では、ときどき、平均的な計算時間を大幅に上回っていることが分かります。
最後に、N を変化させながら上記の試行を繰り返したときの、計算時間の統計量を示します。左のグラフが動的計画法によるもの、右が深さ優先探索によるものです。それぞれ、横軸が下請け会社数、縦軸が計算時間で、先ほどと同様に 1,000 回ずつ実行したときの統計量をプロットしました。それぞれの実行は、実行時間が 3.0 秒に達したところでプロセスを強制終了させて打ち切っています。深さ優先探索のグラフで、いくつかの N で最大値が欠落しているのは、この措置によって計算が打ち切られたためです*3。
[2014-09-13 追記]
上記で紹介しているプログラムでは、least_cost の計算が O(1) にならないため、全体の計算時間は O(2^N) よりも大きくなります。これは、再帰のパラメータとして前回の least_cost の計算結果を渡していくことで、改善できます。そのような工夫を追加したプログラムが以下になります。こちらのプログラムでは、サンプルデータ data_un_50000.txt の計算時間が 0.072 秒となりました。
pohlite-data-generator/solve_depthfirst.cpp at master · y-uti/pohlite-data-generator · GitHub
