Loading article…
コンピュータサイエンスと人工知能において、組み合わせ探索は、一般的に困難であると考えられている問題のインスタンスを、これらのインスタンスの通常大きな解決空間を効率的に探索することによって解決するための探索アルゴリズムを研究します。組み合わせ探索アルゴリズムは、探索空間の有効サイズを縮小するか、ヒューリスティックスを採用することでこの効率を実現します。アルゴリズムの中には、最適な解決策を見つけることが保証されているものもあれば、探索された状態空間の一部で見つかった最良の解決策のみを返すものもあります。
古典的な組み合わせ探索問題には、8 つのクイーンのパズルを解くことや、リバーシやチェスなどの大規模なゲーム ツリーを持つゲームの動きを評価することが含まれます。
計算複雑性理論の研究は、組み合わせ探索の動機付けに役立ちます。組み合わせ探索アルゴリズムは、通常、NP 困難な問題に関係します。このような問題は、一般的には効率的に解決できるとは考えられていません。ただし、複雑性理論のさまざまな近似により、これらの問題のいくつかのインスタンス (たとえば、「小さな」インスタンス) は効率的に解決できることが示唆されています。これは実際に当てはまり、このようなインスタンスは多くの場合、重要な実用的な影響を及ぼします。
例
組み合わせ探索問題を解決するための一般的なアルゴリズムは次のとおりです。
先読み
先読みは組み合わせ探索の重要な要素であり、問題を表すグラフをどの程度深く探索するかを大まかに指定します。先読みに特定の制限が必要なのは、コンピューター チェスやコンピューター 囲碁などの多くのアプリケーションで問題グラフが大きいためです。これらのグラフを単純に幅優先探索すると、最新のコンピューターのメモリがすぐにすべて消費されてしまいます。特定の先読み制限を設定することで、アルゴリズムの時間を慎重に制御できます。先読み制限が増加すると、 アルゴリズムの時間は指数関数的に増加します。
アルファベータプルーニングなどのより洗練された検索手法では、検索ツリーのサブツリー全体を考慮から除外することができます。これらの手法を使用する場合、先読みは正確に定義された量ではなく、検索される最大深度または何らかの平均のいずれかになります。
参照
参考文献
- ラッセルとノーヴィグ。人工知能：現代的なアプローチ。