ホームページへ戻る

第6章: 枝刈り

 「深さ優先探索」も「幅優先探索」もこれまで紹介した例題は探索量の極めて少ない簡単なものでした。従って、探索量の多い問題に前述したアルゴリズムをそのまま当てはめただけでは、答えを発見するまでに膨大な時間がかかってしまいます。

 そこで、無駄な探索を切り捨てる仕掛けが必要になります。これを「枝刈り」といいますが、困ったことに決りきった方法はありません。各問題の特性を分析して個々に対応しなければなりません。そして、これを考えることが「コンピュータプログラミングパズル」の楽しさでもあるのです。概ね、次の3点がポイントになるでしょうか。

1.必要な条件を満たしているか

 枝刈りとは、探索の途中において必要な条件を満たしているかをチェックすることです。必要な条件を満たしていなければ、これ以降の探索は無駄なので引き返します。要するに、チェック可能な必要条件にはどんなものがあるかを見つけ出して、探索プログラムの中にそれを組み込むことです。

2.早い時期に刈った方が効果が大きい

 探索の深さが深くなればなる程、全体の探索量は爆発的に増大していきます。従って、出来るだけ早い時期に枝刈り出来るアイデアを考えつければ劇的な効果が生まれてきます。

3.速くて軽いチェックが必要になる

 枝刈りチェックは探索の過程の中で何度も実行されます。処理の重いチェック法だと場合によってはかえって全体の探索時間が長くなる場合も出てくるので注意が必要です。
 簡単で解り易い具体例を示せれば良いのですが、簡単な例だと「枝刈り」そのものを必要としなくなるので、「Cマガ電脳クラプ」の問題の中から、枝刈りに関して特に印象深かったものを幾つか紹介してみます。(と言っても、枝刈りの雰囲気だけ理解していただければ良いのです)

 カウント・ワン (相反する2つの条件で挟み込め)

 1,2,3・・・Nまでの数字を並べて、その中に1という数字がいくつあるかを数える。つまり、N=1,2,3・・・9までは数字の1は合計1個、N=10で2個、N=11で4個というように数えるわけだ。
 さて、Nまでの数を並べたら、数字の1がちょうどN個含まれていた。このようなNが全部でいくつあるのだろうか。個数を調べてほしい。最初にあてはまるのはN=1ですよ、念のため。

      1995年7月号出題分 (第55回) 吉柄貴樹・三木太郎

 一見して奇妙に思うことは、Nの上限値が示されていないことですがジックリ分析すると10桁を超えるNでは常に[1の個数>N]であることが理論的に導き出せます。(ソースリスト内の説明参照)
 そこで、for (n = 1; n < 10000000000; n++) の中で題意通りに単純に1の個数を数えるようなプログラム記述が考えられますが、これだと探索を終えるのに相当な時間がかかってしまうようです。

 何かいい「枝刈り」はないでしょうか。1の個数はNが増加するにつれて増えていくだけで減ることは無いはずです。ですから、次のことが言えます。

 [1の個数]>[N]の時、その後のNの値に1を全く含まないと仮定しても、
Nがその時の1の個数の値に達するまでは[1の個数]=[N]になることは無い。

 そこで、こんな状態の時は[Nの値]を一気にその時の[1の個数の値]までスキップ出来ます(A)。スキップさせるからには、Nの値からダイレクトにNまでの1の個数を求める関数を用意する必要があります。
 これだけで満足してはいけません。[1の個数]<[N]の時のことも考えましょう。
相反する2つの条件で挟み込むように枝刈りするというのは大変に効果的なのです。

 [1の個数]<[N]の時、その後のNの値が10桁全て1だったと仮定しても、
Nにその差の1/10加算に達するまでは[1の個数]=[N]になることは無い。

 こんな状態の時も[Nの値]を一気に[差の1/10加算値]までスキップさせましょう(B)。いい枝刈り法が見つかりました。この2つの枝刈りに挟み込まれる様にリードされて一瞬に答えを求めてくれました。

     私の応募したソースリスト

 Fペントミノ (枝刈り条件を事前調査)

 3年ほど前に「環状線を作ろう」で登場していただいた石川県松任市の山本浩さん作のパズルです。
 正方形5個を辺同士でつなげてできた図形をペントミノといい、12種類のそれぞれに呼び名がついている。
 右図はそのうちのひとつで、Fペントミノと呼んでいる。
 さて、8×8の盤にFペントミノを11個詰め込めるそうなのだが、回転・裏返しで一致するものを除いて、何通りあるだろうか。
 Fペントミノは裏返して置いてもよいが、マス目に沿って置くものとする。

      1995年12月号出題分 (第60回) 吉柄貴樹・三木太郎

 11個だと5×11=55個のマスを埋めるので、8×8=64の盤では9個のマスが隙間となって残ります。
 従って、探索中において確定した隙間の数を常に数え、その数が許される隙間の数9個を越えてしまったら枝刈りしますが、最後の行(盤の下辺)付近については、どうしても残ってしまう隙間があるはずなのです。
 そこで、ボードの辺寄りにどうしても残ってしまう隙間の最小数を8×4のボード上で事前探索を行い求めておき、9からその値を引いた数、その数こそが本探索中において許される本当の隙間の数となります。
 安易に9個の隙間を許してしまうよりも、かなり効果的に枝刈りを行うことが出来ます。

     私の応募したソースリスト

 三乗の参上 (枝刈りチェック表を設けてみよう)

     
 このA〜Hにそれぞれ違った数を入れて、式として正しく成り立つようにしたい。答はいくつもあるので、それぞれの差、つまりXがいちばん小さくなるものを見付けることにする。ただし、A〜H、そしてXも、すべて正の整数でなければならない。

      1996年10月号出題分 (第70回) 吉柄貴樹

 この問題は、10人いれば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:    }

 これで、当時の私の環境では約6秒で答えを出しました。しかし、HASH[HSIZE] という大きなテーブルを用意しておき、5行目に次の1文を付加してやると、探索は0.2秒で終了しました。たった1行追加するだけの驚くべき高速化でした。

05:  if (++HASH[X%HSIZE] < 4) continue;  

 これは、Xの出現回数をハッシュ値でカウントしています。再ハッシュ計算などしないので、大まかなカウントなのですが、4通りの組が存在する可能性(期待)をチェックするだけなら、これで充分なのです。

     私の応募したソースリスト


ホームページへ戻る