ホーム > 家族のギャラリー > ペントミノを解く > 第6章 ヘキソミノあれこれ > 2. ピースのはめ込み順序による探索数の違い

2. ピースのはめ込み順序による探索数の違い

全ての解を求める場合には、ピースのはめ込み順による探索回数の違いはない（と思う）が、一部の解しか求めない（求められない）場合には、はめ込み順序により探索回数にかなりの差がでる。そこで、ピーステーブルの並び順を、35種のピースの順序と、それぞれピースの配置方向を乱数でシャッフルしてから解いてみた。

以下でいう１回のシャッフルとは、35種のうちの任意の一つを選んで、先頭のピースと入れ替えることと、その任意の一つの中で配置方向の並びを9回入れ替える処理を行っている。例えば、100回のシャッフルとは、ピースの入れ替えを100回行い、各ピース内での配置方向の入れ替えを900回している。これだけ入れ替えればかなりランダムになるのではないかと思う。

100個の解を求める計算を、シャッフル0回（シャッフルしない）から499回迄の500回行い、それぞれについて探索回数を測定した結果が図1-1である。シャッフル回数が少ない場合（ピースがランダムに並んでいない場合）には、探索回数が極端に多い。350回程シャッフルするとかなり探索回数が少なくなる。450回を超えると多少増加するのは使った乱数の性質によるのかもしれない。平均の探索回数は348百万回、平均処理時間は25.7秒（PentiumIII 800MHz)、最小探索回数3百万回で処理時間0.65秒だった。

図2-1 100解を求める際の探索回数の違い

シャッフルしない場合（図2-1 グラフの左端）は極端に探索数が増えることが分かったので、1,000解までの解をシャッフル100回〜499回までで測定してみた結果が図2-2である。X軸の左端の1が図1-1の100回目に対応する。乱数テーブルは同じものを利用している。100解と1,000解で探索回数の傾向は似ている。平均探索回数は1,623百万回、平均処理時間は366秒、最小探索回数は35百万回で処理時間は9.4秒だった。

図2-2 1,000解を求める際の探索回数の違い

1,000解迄の探索数の少ないベスト100シャッフルを選び1万解を求め、さらにその中からベスト10シャッフルを選んで100万解を求めてみた結果が図2-3である。最小探索回数は81,985百万回、処理時間は1時間23分だった。約200解/秒で解けている。

この結果は100万解を求めるまでの探索数と計算時間なので、100万を超えると次第に探索数や計算時間の伸びも増えていき、もっと遅くなっていく。次節で１億回まで求めた結果を示します。

図2-3 100万解を求める際の探索回数の違い