ホーム >
家族のギャラリー >
ペントミノを解く >
第5章 C言語版の高速化あれこれ >
5. 置けるピースと方向を事前計算
5. 置けるピースと方向を事前計算
ピースをボード上に置けるかどうかの探索回数は2千万回近くになっており、この回数を減らすことが高速化に繋がる。一般的に計算量が膨大な場合には、その処理を始める前にできることをやっておくというのが高速なアルゴリズムの王道だ（本当か？）。事前準備の計算量は本番の検査回数の計算量に比べると少なくて済むので、全体の処理時間短縮になる。
2001年2月のヘキソミノプロジェクトで、daichonさんがペントミノで事前計算することをトライした、との記述を見つけたので試してみたら、結構効果がでた。
これはボード上の全ての位置（60ヶ所）について、その位置に置くことができるピースと方向を計算しておくというものだ。例えば、図5-1において、A1座標で L ピースが置ける方向は(a)〜(f)の6通りである。(g),(h)の2つはボードからはみ出すので置けない。これを事前計算しておかないと、ピースを置く際に8通りの置き方を検査する必要がある。つまり、この場合には置けるかどうかの検査数が 6/8 に減少することになる。
この計算を、ボード上の全ての位置（60ヶ所）について、全てのピース（12種）に対して計算しておく。この結果、ピースの置き方は全部で2,024通りであった（意外と少ない）。
 |
 |
 |
| (a) | (b) | (c) |
 |
 |
 |
| (d) | (e) | (f) |
 |
 |
|
| (g) | (h) | |
| 図5-1 置けるピースと方向を事前計算 | ||
この計算を行っておくということは、全てのピースの置き方（2,024通り）のデータを持つということである。このため、各ピースについてボード上の絶対座標を持てることになる。今までは、ピースのボード場での探索の際に配置の基点座標と、ピース内の相対座標の和を計算して探索を行っていたが、この計算を事前計算で行う。これにより1,000万回も行われる探索のときには座標計算なしで置けるようになり、高速化に繋がる。
図5-2に例のように、ピース内の 0,0 が x,y座標を表しており、配置前のピースは、(0,0) を基点とした相対座標でピース形状を表している。このピースをボード上に配置する際に、図5-3のように配置の基点座標値(2,3) を加算する必要がある。この計算を予め行っておき、実際の配置時の計算量を減らす。
 |
 |
|
| 図5-2 ピース内の相対座標 | 図5-3 配置の際の絶対座標 |
以上の事前計算を行ったことにより、５の倍数の空きチェックを行った場合とほぼ同じ探索回数（1千百万回）になり、速くなった。事前計算の時間も処理時間に含めていますが、事前計算にかかる時間は探索時間に比べると非常に少ないです。