力まかせ探索

力まかせ探索（ちからまかせたんさく、Brute-force search）またはしらみつぶし探索（Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では <math>64! / 56! = 178,462,987,637,760</math>通りの配置を全て順にチェックしていく。バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。力まかせ探索は実装が簡単で、解があるなら絶対それを発見できる。しかし、そのコストは潜在的な解候補数に比例し、多くの実際の問題では、問題の規模に対して解候補数が組合せ爆発を起こして急激に増大する傾向がある。従って力まかせ探索が使われるのは、問題の大きさが限定されている場合か、解候補数を処理可能な程度に縮小できる問題固有のヒューリスティクスがある場合である。また、実装の単純さが問題を解く速度よりも重要な場合にも使われる。これは例えば、アルゴリズムの間違いが深刻な影響を及ぼすような重要なアプリケーションや、数学的定理をコンピュータで証明するときである。力まかせ探索は、各種アルゴリズムやメタヒューリスティクスのベンチマーク比較を行うときの基準値としても用いられる。実際、力まかせ探索は最も単純なメタヒューリスティクスと見ることもできる。