状態空間検索

探索アルゴリズムのクラス

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

問題は多くの場合、状態空間、つまり問題が取り得る状態の集合としてモデル化されます。状態の集合は、最初の状態を2番目の状態に変換するために実行できる操作がある場合、2つの状態が接続されたグラフを形成します。

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

表現

状態空間探索では、状態空間は正式にはタプル として表現されます。 ${\displaystyle S:\langle S,A,\operatorname {Action} (s),\operatorname {Result} (s,a),\operatorname {Cost} (s,a)\rangle }$

• ${\displaystyle S}$はすべての可能な状態の集合です
• ${\displaystyle A}$は、特定の状態ではなく、状態空間全体に関する可能なアクションの集合です。
• ${\displaystyle \operatorname {Action} (s)}$は、特定の状態において実行可能なアクションを決定する関数です。
• ${\displaystyle \operatorname {Result} (s,a)}$は、状態 でアクションを実行したときに到達した状態を返す関数です。 ${\displaystyle a}$ ${\displaystyle s}$
• ${\displaystyle \operatorname {Cost} (s,a)}$は、状態 でアクションを実行するためのコストです。多くの状態空間ではは定数ですが、常にそうであるとは限りません。 ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle a}$

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

無情報探索

PooleとMackworthによると、以下は無情報状態空間探索法であり、目標の位置に関する事前情報を持たないことを意味します。^[1]

• 従来の深さ優先探索
• 幅優先探索
• 反復深化
• 最低コスト優先探索／均一コスト探索（UCS）

インフォームド探索

これらの手法は、目標の位置をヒューリスティック関数の形で受け取ります。^[2] PooleとMackworthは、インフォームド探索アルゴリズムとして以下の例を挙げています

• インフォームド/ヒューリスティック深さ優先探索
• 貪欲最良優先探索
• A*探索

参照

• 状態空間
• 状態空間プランニング
• 分枝限定法- 状態空間探索のサブセットを刈り込むことで、状態空間探索をより効率的にする方法

参考文献

1. Poole, David; Mackworth, Alan. 「3.5 無情報探索戦略 ‣ 第3章 解決策の探索 ‣ 人工知能：計算エージェントの基礎 第2版」artint.info 。 2017年12月7日閲覧。
2. Poole, David; Mackworth, Alan. 「3.6 ヒューリスティック探索 ‣ 第3章 解決策の探索 ‣ 人工知能：計算エージェントの基礎 第2版」artint.info 。 2017年12月7日閲覧。

• Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach . Prentice Hall.

Retrieved from "https://en.wikipedia.org/w/index.php?title=State-space_search&oldid=1290966989"