力まかせ探索
バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。
力まかせ探索は実装が簡単で、解があるなら絶対それを発見できる。しかし、そのコストは潜在的な解候補数に比例し、多くの実際の問題では、問題の規模に対して解候補数が組合せ爆発を起こして急激に増大する傾向がある。従って力まかせ探索が使われるのは、問題の大きさが限定されている場合か、解候補数を処理可能な程度に縮小できる問題固有のヒューリスティクスがある場合である。
また、実装の単純さが問題を解く速度よりも重要な場合にも使われる。これは例えば、アルゴリズムの間違いが深刻な影響を及ぼすような重要なアプリケーションや、数学的定理をコンピュータで証明するときである。力まかせ探索は、各種アルゴリズムやメタヒューリスティクスのベンチマーク比較を行うときの基準値としても用いられる。実際、力まかせ探索は最も単純なメタヒューリスティクスと見ることもできる。
力まかせ探索(ちからまかせたんさく、英: Brute-force search)またはしらみつぶし探索(英: Exhaustive search)は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。
バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 64 ! / 56 ! = 178 , 462 , 987 , 637 , 760 {\displaystyle 64!/56!=178,462,987,637,760} 通りの配置を全て順にチェックしていく。
さらに、これらの値は全て違う値でなければならないので、解候補数は 1 から 8 までの整数の順列にまで削減される。つまり 8! = 40,320 であり、これは当初の解候補数の10万分の1である。
この例で判るとおり、ちょっとした問題の分析で解候補数が劇的に削減できることが多く、解けない問題が簡単な問題になる。またこの例では、制限された解候補を数え上げる方法(first と next で順に解候補を生成する方法)もオリジナルと比較して複雑化していない。
場合によっては、問題の分析によって解候補が全て妥当な解となるような制限を発見できることもある。すなわちそれは、全ての解を列挙できる新たなアルゴリズムであり、力まかせ探索とは異なるものである。例として、2つの単語が互いのアナグラムかどうかをチェックする問題を考えてみよう。単純に力まかせ探索を行うなら、一方の単語の文字の全ての可能な並べ替えを生成することになるだろう。しかし、この問題はそれぞれの単語の文字をソートしたり字種ごとにカウントすることで簡単に比較可能となり、力まかせ探索を必要としない。