力まかせ探索

力まかせ探索（ちからまかせたんさく、英: Brute-force search）またはしらみつぶし探索（英: Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。

バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では ${\displaystyle 64!/56!=178,462,987,637,760}$通りの配置を全て順にチェックしていく。バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。

力まかせ探索は実装が簡単で、解があるなら絶対それを発見できる。しかし、そのコストは潜在的な解候補数に比例し、多くの実際の問題では、問題の規模に対して解候補数が組合せ爆発を起こして急激に増大する傾向がある。従って力まかせ探索が使われるのは、問題の大きさが限定されている場合か、解候補数を処理可能な程度に縮小できる問題固有のヒューリスティクスがある場合である。

また、実装の単純さが問題を解く速度よりも重要な場合にも使われる。これは例えば、アルゴリズムの間違いが深刻な影響を及ぼすような重要なアプリケーションや、数学的定理をコンピュータで証明するときである。力まかせ探索は、各種アルゴリズムやメタヒューリスティクスのベンチマーク比較を行うときの基準値としても用いられる。実際、力まかせ探索は最も単純なメタヒューリスティクスと見ることもできる。

力まかせ探索の実装[編集]

基本アルゴリズム[編集]

特定の問題に力まかせ探索を適用するには、4つのプロシージャ first、next、valid、output を実装しなければならない。これらのプロシージャは引数として解くべき問題についてのデータ P をとり、以下のことを行う。

1. first (P): P の最初の解候補を生成する。
2. next (P, c): 現在の解候補 c の次の解候補を生成する。
3. valid (P, c): 解候補 c が P の解かどうかをチェックする。
4. output (P, c): P の解として c を適切に表示したり、他のアプリケーションに渡したりする。

next は P の解候補がもう存在しない場合には、それを通知しなければならない。簡単な方法としては、空の解候補として他の解候補では決して使われないデータ値 Λ を使えばよい。同様に first も P の解候補が全く存在しない場合には Λ を返す。以上から、力まかせ探索をアルゴリズム的に表すと、次のようになる。

c ${\displaystyle \gets }$ first(P) while c ${\displaystyle \neq }$ Λ do   if valid(P,c) then output(P, c)   c ${\displaystyle \gets }$ next(P,c) 

例えば、整数 n の約数を求める場合、問題インスタンスデータ P はその整数 n となる。first (n) を呼び出した場合、n ${\displaystyle \geq }$ 1 なら 1 を返し、そうでない場合は Λ を返す。next (n,c) を呼び出した場合、c ${\displaystyle <}$ n なら c + 1 を返し、そうでない場合はΛを返す。valid (n,c) は c が n の約数ならば true を返す。なお、Λとして n + 1 を返すようにすれば、実装がかなり単純化される。

典型的な派生[編集]

上記の力まかせ探索のアルゴリズムでは、P の解が見つかるたびに output を呼び出している。最初の解を見つけたときや、指定された個数の解を見つけたとき、停止するよう変更することは容易である。また、指定された個数の解候補をチェックしたときや、指定されたCPU時間を消費した時点で停止させるのも容易である。

組合せ爆発[編集]

力まかせ探索の主な欠点は、多くの実際の問題では解候補数が極めて多数になってしまうという点である。

例えば、上述のようにある数値の約数を求める場合、解候補数は指定された数値 n によって決まる。従って n が十進で16桁なら、探索には少なくとも 10¹⁵ 個の機械語命令を費やすことになり、これは一般的なPCでは数日に及ぶ。n が無作為な64ビットの自然数なら、十進では平均で19桁となり、探索には約10年かかる。

この解候補数の急激な増大は、どんな問題でも発生しうる。例えば、10文字の並べ替えをして特定の並びを見つける場合、10! = 3,628,800個の解候補があることになるが、この程度ならばPCで1秒以内に生成してチェックできる。しかし、たった1文字追加して問題のデータサイズが10%増加しただけで、解候補数は1000%の増大になる。20文字になると解候補数は 20! すなわち約 2.4×10¹⁸ であり、これを探索するには約1万年かかる。この好ましくない現象を一般に組合せ爆発と呼ぶ。

力まかせ探索の高速化[編集]

力まかせ探索のアルゴリズムを高速化する方法として、その問題に特有のヒューリスティクスを使って探索空間（すなわち解候補集合）を狭める方法がある。

例えば、エイト・クイーンの場合を考えてみよう。2つ以上のクイーンを同じマスに置けないという事実を使えば、考慮すべき組合せは64個のマスから8個のマスを選ぶことに他ならず、解候補数は 64!/56!/8! = 4,426,165,368 となる。

さらにもっと考察すれば、2つのクイーンが同じ行や列に配置されていれば、解にはならないということも言える。従って、さらに解候補を制限することができ、クイーン1は行1に、クイーン2は行2に、というようにそれぞれが別の行になるよう配置すればよい。このような配置をするには、配置を8要素の配列（c[1] から c[8]）で表し、それぞれの要素は 1 から 8 までの値をとるようにする。従って、c[1] にはクイーン1の列番号、c[2] にはクイーン2の列番号というふうに格納する。さらに、これらの値は全て違う値でなければならないので、解候補数は 1 から 8 までの整数の順列にまで削減される。つまり 8! = 40,320 であり、これは当初の解候補数の10万分の1である。

この例で判るとおり、ちょっとした問題の分析で解候補数が劇的に削減できることが多く、解けない問題が簡単な問題になる。またこの例では、制限された解候補を数え上げる方法（first と next で順に解候補を生成する方法）もオリジナルと比較して複雑化していない。

場合によっては、問題の分析によって解候補が全て妥当な解となるような制限を発見できることもある。すなわちそれは、全ての解を列挙できる新たなアルゴリズムであり、力まかせ探索とは異なるものである。例として、2つの単語が互いのアナグラムかどうかをチェックする問題を考えてみよう。単純に力まかせ探索を行うなら、一方の単語の文字の全ての可能な並べ替えを生成することになるだろう。しかし、この問題はそれぞれの単語の文字をソートしたり字種ごとにカウントすることで簡単に比較可能となり、力まかせ探索を必要としない。

探索空間の並べ替え[編集]

全ての解ではなく1つの解が得られればよい場合、力まかせ探索の実行時間の期待値は、解候補を生成する順序に左右される。一般原則として、最も可能性が高い候補からチェックすべきである。例えば無作為な数 n の約数を探す場合、n が c で割り切れる確率は 1/c だから、解候補は小さいほう（つまり 2）からチェックしたほうが逆の順序よりも効率的である。

さらに、正しい解が得られる確率は、それまでの失敗した履歴に影響されることが多い。例えば、1000ビットのビット列 P から値が 1 のビットを探す問題を考えてみよう。この場合、候補としてインデックスを 1 から 1000 まで変化させ、その候補 c が P[c] = 1 のとき解と判定される。ここで、P の先頭ビットが 0 または 1 である確率が等しく、その後のビットはその直前のビットと同じである確率が90%だとする。解候補を 1 から 1000 に順次インクリメントしていった場合、解が得られるまでの候補数の平均は約 6 となる。一方、1,11,21,31...991,2,12,22,32 のように解候補を生成すると、解が得られるまでの候補数の平均は 2 より若干大きいだけである。

さらに一般化すれば、探索空間の数え上げは、それまでの候補が解でなかったという事実を考慮して、次の候補が最も妥当と思われるものとなるよう選ぶべきである。したがって、例えば解が何らかの意味で「かたまって」存在するなら、新しい解候補はそれまでの候補からなるべく遠いものとすべきである。逆に解が「散らばっている」なら、それまでの候補に近いものを順次試したほうがよい。

代替方式[編集]

他にも探索手法やメタヒューリスティクスは多数存在し、解に関する様々な知識を利用するよう設計されている。

ヒューリスティクスは、探索の一部を早めに切り捨てるのにも使われる。例として、ゲーム理論におけるミニマックス法がある。これは、探索の初期段階で多くの部分木を排除する。

構文解析などの分野では、チャートパーサなどの技法が問題の制約条件を利用して、指数関数的複雑さの問題を多項式レベルの複雑さの問題に削減している。

問題の探索空間は、問題を単純化することでも削減できる。例えばコンピュータチェスでは、ある手数で木を刈り込み、残りの木を評価関数で近似することで、完全なミニマックス法の探索木よりもさらに限定された探索木を求めることができる。

関連項目[編集]

• 総当たり攻撃
• ランダウの記号