力まかせ探索の高速化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/08/21 17:51 UTC 版)
「力まかせ探索」の記事における「力まかせ探索の高速化」の解説
力まかせ探索のアルゴリズムを高速化する方法として、その問題に特有のヒューリスティクスを使って探索空間（すなわち解候補集合）を狭める方法がある。 例えば、エイト・クイーンの場合を考えてみよう。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つの単語が互いのアナグラムかどうかをチェックする問題を考えてみよう。単純に力まかせ探索を行うなら、一方の単語の文字の全ての可能な並べ替えを生成することになるだろう。しかし、この問題はそれぞれの単語の文字をソートしたり字種ごとにカウントすることで簡単に比較可能となり、力まかせ探索を必要としない。
※この「力まかせ探索の高速化」の解説は、「力まかせ探索」の解説の一部です。
「力まかせ探索の高速化」を含む「力まかせ探索」の記事については、「力まかせ探索」の概要を参照ください。
- 力まかせ探索の高速化のページへのリンク
