ホーム >
家族のギャラリー >
ペントミノを解く >
第5章 C言語版の高速化あれこれ >
10. 次に置く場所の孤立(1,2個)チェックのパターン限定
10. 次に置く場所の孤立(1,2個)チェックのパターン限定
2. 次に置く場所の孤立(1,2個)チェックで説明したように、無駄な探索を防ぐために、次に置く場所が1個または2個しかスペースがない場合のチェックを行っている。これは、図10-1 (a)〜(c)に示すパターンのチェックを行っている。赤い×が配置の基点座標で、この座標の左側及び上側はすでにピースが置いてあるはずなので、マゼンタの座標が埋まっているかをチェックすればよい。
すると、1個 及び 2個×2パターンをチェックするために合計 9ヶ所が埋まっていることを確認することになる。つまり9回の判定が必要になる。図10-1をよく見ると、図(a)の座標(2)と、図(b)の座標(2)は共通なので1回のチェックで済ませられる。同様に、図(b)の(3)と、図(c)の(3)も共通となる。
しかし、図(c)のパターンの検査は、埋まっているかの判断が4回必要で(a),(b)に比べると検査のコストが高いのがわかる。そこで、検査パターンを(a),(b)に限定し、さらに(2)を共通項としてくくり出すと判定回数は 4回で済み当初に比べると4/9に減る。
図(c)のパターンをチェックしなくなることにより、探索回数が868万回から930万回へと63万回ほど増加するが、判定回数が減ったことにより全体の処理時間は減少した。
 |
 |
 |
| (a) | (b) | (c) |
| 図10-1 次に置く場所の孤立チェック | ||