パズル問題解法のアルゴリズム講座
応用編
枝 刈 り
そこで、無駄な探索を切り捨てる仕掛けが必要になります。これを「枝刈り」といいますが、困ったことに決りきった方法はありません。各問題の特性を分析して個々に対応しなければなりません。そして、これを考えることが「コンピュータプログラミングパズル」の楽しさでもあるのです。概ね、次の３点がポイントになるでしょうか。
１．必要な条件を満たしているか
枝刈りとは、探索の途中において必要な条件を満たしているかをチェックすることです。言い替えると、チェック可能な必要条件にはどんなものがあるかをひねり出して、探索プログラムの中に組み込むことです。
２．早い時期に刈った方が効果が大きい
探索の深さが深くなればなる程、全体の探索量は爆発的に増大していきます。従って、出来るだけ早い時期に枝刈り出来るアイデアを考えつければ劇的な効果が生まれてきます。
３．速くて軽いチェックが必要になる
枝刈りチェックは探索の過程の中で何度も実行されます。処理の重いチェック法だと場合によってはかえって全体の探索時間が長くなる場合も出てくるので注意が必要です。
簡単で解り易い具体例を示せれば良いのですが、簡単な例だと「枝刈り」そのものを必要としなくなるので、「Ｃマガ電脳クラプ」の問題の中から、枝刈りに関して特に印象深かったものを幾つか紹介してみます。(と言っても、枝刈りの雰囲気だけ理解していただければ良いのです)
| カウント・ワン (相反する２つの条件で挟み込め) |
|
１，２，３・・・Ｎまでの数字を並べて、その中に１という数字がいくつあるかを数える。つまり、Ｎ＝１，２，３・・・９までは数字の１は合計１個、Ｎ＝１０で２個、Ｎ＝１１で４個というように数えるわけだ。 さて、Ｎまでの数を並べたら、数字の１がちょうどＮ個含まれていた。このようなＮが全部でいくつあるのだろうか。個数を調べてほしい。最初にあてはまるのはＮ＝１ですよ、念のため。 1995年7月号出題分 (第５５回) 吉柄貴樹・三木太郎 |
一見して奇妙に思うことは、Ｎの上限値が示されていないことですがジックリ分析すると１０桁を超えるＮでは常に[１の個数＞Ｎ]であることが理論的に導き出せます。(ソースリスト内の説明参照)
そこで、for (n = 1; n < 10000000000; n++) の中で題意通りに単純に１の個数を数えるようなプログラム記述が考えられますが、これだと探索を終えるのに相当な時間がかかってしまうようです。
何かいい「枝刈り」はないでしょうか。１の個数はＮが増加するにつれて増えていくだけで減ることは無いはずです。ですから、次のことが言えます。
[1の個数]＞[N]の時、その後のNの値に1を全く含まないと仮定しても、
Nがその時の1の個数の値に達するまでは[1の個数]＝[N]になることは無い。そこで、こんな状態の時は[Nの値]を一気にその時の[1の個数の値]までスキップ出来ます(Ａ)。スキップさせるからには、Nの値からダイレクトにNまでの1の個数を求める関数を用意する必要があります。
これだけで満足してはいけません。[1の個数]＜[N]の時のことも考えましょう。相反する２つの条件で挟み込むように枝刈りするというのは大変に効果的なのです。[1の個数]＜[N]の時、その後のNの値が10桁全て1だったと仮定しても、
Nにその差の1/10加算に達するまでは[1の個数]＝[N]になることは無い。こんな状態の時も[Nの値]を一気に[差の1/10加算値]までスキップさせましょう(Ｂ)。いい枝刈り法が見つかりましたネ。この２つの枝刈りに挟み込まれる様にリードされて一瞬に答えを求めてくれます。
| Ｆペントミノ (枝刈り条件を事前調査) |
３年ほど前に「環状線を作ろう」で登場していただいた石川県松任市の山本浩さん作のパズルです。
正方形５個を辺同士でつなげてできた図形をペントミノといい、１２種類のそれぞれに呼び名がついている。右図はそのうちのひとつで、Ｆペントミノと呼んでいる。 さて、８×８の盤にＦペントミノを１１個詰め込めるそうなのだが、回転・裏返しで一致するものを除いて、何通りあるだろうか。 Ｆペントミノは裏返して置いてもよいが、マス目に沿って置くものとする。 1995年12月号出題分 (第６０回) 吉柄貴樹・三木太郎 |
１１個だと５×１１＝５５個のマスを埋めるので、８×８＝６４の盤では９個のマスが隙間となって残ります。
従って、探索中において確定した隙間の数を常に数え、その数が許される隙間の数を越えてしまったら枝刈りしますが、最後の行(盤の下辺)付近については、どうしても残ってしまう隙間があるはずなのです。
そこで、ボードの辺寄りにどうしても残ってしまう隙間の最小数を８×４のボード上で事前探索を行い求めておき、９からその値を引いた数、その数こそが本探索中において許される隙間の数となります。
安易に９個の隙間を許してしまうよりも、かなり効果的に枝刈りを行うことが出来ます。
| 三乗の参上 (枝刈りチェック表を設けてみよう) |
 このＡ〜Ｈにそれぞれ違った数を入れて、式として正しく成り立つようにしたい。答はいくつもあるので、それぞれの差、つまりＸがいちばん小さくなるものを見付けることにする。ただし、Ａ〜Ｈ、そしてＸも、すべて正の整数でなければならない。 1996年10月号出題分 (第７０回) 吉柄貴樹 |
この問題は、１０人いれば１０種類のプログラムが登場してもおかしくない程、いろいろなアプローチが考えられますが、私は、多重ループ検索という極めて単純なアルゴリズムを用いたのだが....。
01: /* A,B,Xの組合せを生成 */ 02: for (A=1; ;A++) 03: for (B=A-1; B; B--) { 04: X = A*A*A - B*B*B; 05: 06: /* C,Dの組合せを探す */ 07: for (C,Dの組をA,Bの降方に探す) { 08: 09: /* E,Fの組合せを探す */ 10: for (E,Fの組をC,Dの降方に探す) { 11: 12: /* G,Hの組合せを探す */ 13: for (G,Hの組をE,Fの降方に探す) { 14: 15: A,B,...H,Xを記録; 16: } 17: } 18: } 19: }これで、当時の私の環境では約６秒で答えを出した。しかし、HASH[HSIZE] という大きなテーブルを用意しておき、５行目に次の１文を付加してやると、探索は０．２秒で終了した。たった１行だけの驚くべき高速化である。
これは、Xの出現回数をハッシュ値でカウントしているのだ。再ハッシュ計算などしないので、大まかなカウントなのだが、４通りの組が存在する可能性(期待)をチェックするだけなら、これで充分なのである。
05: if (++HASH[X%HSIZE] < 4) continue;