ステートスペースサーチ - 百科事典

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

問題は通常、状態空間としてモデル化されます。これは、問題が存在できる状態の集合です。状態の集合はグラフを形成し、1つの状態が別の状態に変換できる操作がある場合、2つの状態が接続されます。

状態空間探索は、状態空間が暗黙的であるため、従来のコンピュータサイエンスの探索方法とは異なります：典型的な状態空間グラフは非常に大きく、メモリで生成および保存することができません。その代わりに、ノードは探索中に生成され、その後通常は破棄されます。組み合わせ探索インスタンスの解は、目標状態自体または初期状態から目標状態へのパスで構成されることがあります。

表現
状態空間探索では、状態空間は形式的に以下のタプルとして表されます：



S
:
⟨
S
,
A
,
Action
⁡
(
s
)
,
Result
⁡
(
s
,
a
)
,
Cost
⁡
(
s
,
a
)
⟩


{\displaystyle S:\langle S,A,\operatorname {Action} (s),\operatorname {Result} (s,a),\operatorname {Cost} (s,a)\rangle }

、以下の通りです：




S


{\displaystyle S}

は、すべての可能な状態の集合です；



A


{\displaystyle A}

は、特定の状態に関連しない可能性のある行動の集合であり、状態空間全体に関連しています；



Action
⁡
(
s
)


{\displaystyle \operatorname {Action} (s)}

は、ある状態でどの行動が実行可能かを決定する関数です；



Result
⁡
(
s
,
a
)


{\displaystyle \operatorname {Result} (s,a)}

は、状態 s で行動 a を実行したときに達する状態を返す関数です；



Cost
⁡
(
s
,
a
)


{\displaystyle \operatorname {Cost} (s,a)}

は、状態 s で行動 a を実行するコストです。多くの状態空間では、a は定数ですが、これは常にそうではありません。

状態空間探索アルゴリズムの例


= 无情報探索 =
PooleとMackworthによると、以下は無情報状態空間探索方法であり、目標の場所に関する前情報を持っていないことを意味します。

従来の深度優先探索
幅優先探索
再帰的深化
最低コスト優先探索 / 一貫コスト探索（UCS）

= 有情報探索 =
これらの方法は、目標の場所をヒューリスティック関数の形で取り入れます。PooleとMackworthは以下を有情報探索アルゴリズムとして挙げています：

有情報/ヒューリスティック深度優先探索
greedy best-first search
A* search

参考リソース
State space
State-space planning
枝刈りおよびバウンド - 状態空間探索を効率的にするための方法

参考文献
Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.