状態空間探索

状態空間探索は、人工知能（AI）を含むコンピュータ科学の分野で使用されるプロセスであり、インスタンスの連続的な構成または状態を考慮し、望ましい特性を持つ目標状態を見つけることを目的としている。

問題はしばしば状態空間、つまり問題が取りうる状態の集合としてモデル化される。状態の集合はグラフを形成し、ある操作によって一方の状態を他方の状態に変換できる場合、その2つの状態はグラフ上で接続される。

状態空間探索は、状態空間が暗黙的であるという点で、従来のコンピュータサイエンスの探索手法とは大きく異なります。典型的な状態空間グラフは、生成してメモリに格納するには大きすぎるためです。代わりに、ノードは探索されるにつれて生成され、通常はその後破棄されます。組み合わせ探索インスタンスの解は、目標状態そのもの、または何らかの初期状態から目標状態への経路で構成される場合があります。

状態空間探索では、状態空間は形式的にタプルとして表現される。${\displaystyle S:\langle S,A,\operatorname {アクション} (s),\operatorname {結果} (s,a),\operatorname {コスト} (s,a)\rangle }$具体的には：

• ${\displaystyle S}$は、すべての可能な状態の集合です。
• ${\displaystyle A}$これは、特定の状態に関連するものではなく、状態空間全体に関する可能な行動の集合です。
• ${\displaystyle \operatorname {アクション} (s)}$特定の状態において実行可能なアクションを決定する機能である。
• ${\displaystyle \operatorname {Result} (s,a)}$アクションを実行した際に到達した状態を返す関数です。${\displaystyle a}$州内${\displaystyle s}$;
• ${\displaystyle \operatorname {コスト} (s,a)}$行動を実行するコスト${\displaystyle a}$州内${\displaystyle s}$多くの国家空間において、${\displaystyle a}$は定数であるが、これは常に正しいとは限らない。

• 状態空間
• 状態空間計画
• 分枝限定法– 状態空間のサブセットを剪定することで、状態空間探索をより効率的にする方法

• スチュアート・J・ラッセル、ピーター・ノーヴィグ（1995）。人工知能：現代的アプローチ。プレンティス・ホール。