|
力まかせ探索（ちからまかせたんさく、）またはしらみつぶし探索（）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 通りの配置を全て順にチェックしていく。バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。 力まかせ探索は実装が簡単で、解があるなら絶対それを発見できる。しかし、そのコストは潜在的な解候補数に比例し、多くの実際の問題では、問題の規模に対して解候補数が組合せ爆発を起こして急激に増大する傾向がある。従って力まかせ探索が使われるのは、問題の大きさが限定されている場合か、解候補数を処理可能な程度に縮小できる問題固有のヒューリスティクスがある場合である。 また、実装の単純さが問題を解く速度よりも重要な場合にも使われる。これは例えば、アルゴリズムの間違いが深刻な影響を及ぼすような重要なアプリケーションや、数学的定理をコンピュータで証明するときである。力まかせ探索は、各種アルゴリズムやメタヒューリスティクスのベンチマーク比較を行うときの基準値としても用いられる。実際、力まかせ探索は最も単純なメタヒューリスティクスと見ることもできる。 == 力まかせ探索の実装 == === 基本アルゴリズム === 特定の問題に力まかせ探索を適用するには、4つのプロシージャ ''first''、''next''、''valid''、''output'' を実装しなければならない。これらのプロシージャは引数として解くべき問題についてのデータ ''P'' をとり、以下のことを行う。 # ''first'' (''P''): ''P'' の最初の解候補を生成する。 # ''next'' (''P'', ''c''): 現在の解候補 ''c'' の次の解候補を生成する。 # ''valid'' (''P'', ''c''): 解候補 ''c'' が ''P'' の解かどうかをチェックする。 # ''output'' (''P'', ''c''): ''P'' の解として ''c'' を適切に表示したり、他のアプリケーションに渡したりする。 ''next'' は ''P'' の解候補がもう存在しない場合には、それを通知しなければならない。簡単な方法としては、空の解候補として他の解候補では決して使われないデータ値 Λ を使えばよい。同様に ''first'' も ''P'' の解候補が全く存在しない場合には Λ を返す。以上から、力まかせ探索をアルゴリズム的に表すと、次のようになる。 ''c'' ''first''(''P'') while ''c'' Λ ''do'' if ''valid''(''P'',''c'') then ''output''(''P'', ''c'') ''c'' ''next''(''P'',''c'') 例えば、整数 ''n'' の約数を求める場合、問題インスタンスデータ ''P'' はその整数 ''n'' となる。''first'' (''n'') を呼び出した場合、''n'' 1 なら 1 を返し、そうでない場合は Λ を返す。''next'' (''n'',''c'') を呼び出した場合、''c'' ''n'' なら ''c'' + 1 を返し、そうでない場合はΛを返す。''valid'' (''n'',''c'') は ''c'' が ''n'' の約数ならば true を返す。なお、Λとして ''n'' + 1 を返すようにすれば、実装がかなり単純化される。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「力まかせ探索」の詳細全文を読む スポンサード リンク
|