ホーム > 家族のギャラリー > ペントミノを解く > 第6章 ヘキソミノあれこれ > 3. 1億解までの探索数の変化

3. 1億解までの探索数の変化

前節で実験した100万解を求めるのに最適なピース順序を使って1億解まで計算してみた。図2-1が100万解毎に探索数と解を出力させて、計100回分の探索数をプロットしたグラフです。
図2-1 1億解を求める迄の100万解毎の探索回数

最初の100万解(1〜100万)は、探索回数が約800億回と一番少ない。これは前節の実験結果を反映したものなので当然である。その後、徐々に探索回数が増加しているが、平均すると3,000億回あたりである。途中、8,000億回近くのピークがあったりして、無用な探索が多く行われていることがうかがえます。

1億解を求めるのに要した時間は、Pentium3 1GHzマシンで約600時間(25日)、探索回数の合計は2.85×10^13回であり、約30万回調べて一つの解が求まっています。探索速度は秒速1,320万回、解が求まる速度は秒速46解となり、100万解を求めたときより遅くなっている。

仮にPentiumのCPI(Cycle Per Instruction)=1と仮定すると1回の探索に75命令要している計算になる。CPIは1よりは少ないと思われるので200命令以上かかっているかも。とにかくアセンブラや論理演算などを使って探索の命令数を減らすにも限度があるので、探索枝を刈り込む手法を考えないと高速化には繋がらない。

1回の探索に要する200命令を20命令に減らすのは無理だが、探索回数の30万回を3万回に減らすのは頑張ればできそう(な気がする)。それでも1/10の高速化にしかならないが。

【↑インデックス】  【←前】  【→次】