Combinatorial search とは

コンピュータサイエンスと人工知能では、コンビナトリアルサーチ研究は、これらのインスタンスの通常大きなソリューションスペースを効率的に探索することによって、一般的に難しいと考えられるインスタンスの問題を解決するアルゴリズムを検索します。組み合わせ探索アルゴリズムは、探索空間の有効サイズを縮小するか、または発見的手法を採用することによって、この効率を達成する。アルゴリズムによっては最適解を見つけることが保証されているものもあれば、探索された状態空間の部分で見つかった最良解のみを返すものもあります。
クラシックなコンビナトリアル検索の問題には、8つのクイーンパズルを解くこと、またはリバーシやチェスのような大きなゲームツリーを使ってゲームの動きを評価することが含まれます。
計算複雑性理論の研究は、コンビナトリアル検索を動機づけるのに役立つ。組み合わせ探索アルゴリズムは、通常、NP困難な問題に関係している。このような問題は、一般的には効率的に解決できるとは考えられていない。しかしながら、複雑さ理論の様々な近似は、これらの問題のいくつかの例(例えば、「小さな」例)が効率的に解けることを示唆している。これは事実であり、そのような例はしばしば重要な実用的な影響を有する。